Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

# MAL : closures and recursion

53 views

### none albert

Aug 19, 2023, 10:24:17â€¯AM8/19/23
to
https://github.com/kanaka/mal/

I'm trying to Make Another Lisp using ciforth lina/wina/xina.

I run in a bit of trouble in the interaction between closures and recursion.

I succeeded in handling closure in
( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
In lisp we have
(fn* (fn* (b) (+ a b))) 5)
in a sort of limbo. It can be only half evaluated, because b is 5 but no
decision has been made what `a actually means. (A "free" variable).
Only by encapsulating it in an "environment" where `a has the value
7 one can proceed.
Indeed is ((fn*..) 5) now evaluated in an environment where `a
is still valid. This is done by storing the then-current
environment chain (referring to all its outer
environments) in the function structure created by the second call
of fn* and restoring prior to execution.
Of course every creation and every call will suffer a similar
overhead, so the first and the third suffer too.
This works and the answer is 12.

However this "solution" gets me in the woods with recursion
(def! sumdown (fn* (N) (if (> N 0) (+ N (sumdown (- N 1))) 0)))

As soon as you do
(sumdown 1)
you get an environment where N:1 and you got to calculate
(+ N (sumdown (-N 1)))
The first `N is not the problem, but
now upon entering sumdown, the environment is restored/destroyed
and N is nowhere to be seen.

The solution i found is the following.
Case ...I is a weird exception. Exception! That is the keyword.
So the idea is to evaluate (fn* (b) (+ a b))) 5) as if your nose bleeds,
and then discover ERROR 8010 (symbol not found), for `a is not there.
Now you lift the not-found symbol `a from the stored environment to the
inner environment and evaluate again.
Hopefully the inner environment is to be thrown away expeditiously.
The overhead for recursion is limited by storing a pointer in the
header of a function such as sumdown or fibonacci. This happens one
time during compilation (or whatever the lisp term is) and the pointer
need never be inspected.

Coming back to ... I
A weird situation arises if in the meantime a function is called that
has a separate and distinct `a (free) in the environment it was
created in. Let's hope this doesn't happen.
[Why bother, people who write such programs had it coming.
The least they have to do is to rename `a to
TheDelayInMSBeforeDrawingTheBottomLineInaPurpleCaptionBox
diminishing the risk for a name clash.]

What do you all think?

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

### Kaz Kylheku

Aug 19, 2023, 11:41:34â€¯AM8/19/23
to
On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
> https://github.com/kanaka/mal/
>
> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>
> I run in a bit of trouble in the interaction between closures and recursion.
>
> I succeeded in handling closure in
> ( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
> In lisp we have
> (fn* (fn* (b) (+ a b))) 5)
^ ^

These parentheses balance; the dangling 5) then belongs with something
else.

Is fn* the lambda operator? If so, (lambda (lambda (b) ...)) doesn't
make sense; the outer lambda is specifying a function whose first
parameter is named lambda and whose second parameter is the list (b).

> Indeed is ((fn*..) 5) now evaluated in an environment where `a
> is still valid.

A lambda that is invoked immediately can be evaluated without
any lexical closure being created, or even a function call
taking place. It can be converted to let.

((lambda (b) (+ a b) 5))

is equivalent to

(let ((b 5))
(+ a b))

Under this transformation, the environment is literally "still valid".

If the closure is earnestly made and invoked, then the invocation of the
function is often not made in an environment in which the captured
variables are still valid. That is not assumed. A captured version of
that environment is mounted in place by the function call mechanism,
as you note here:

> This is done by storing the then-current
> environment chain (referring to all its outer
> environments) in the function structure created by the second call
> of fn* and restoring prior to execution.

> Of course every creation and every call will suffer a similar
> overhead, so the first and the third suffer too.

You can remove the function call overhead for trivial lambdas
that are called immediately upon being born, by converting them
to let (if you have let, and if it's not itself implemented
using lambda).

> However this "solution" gets me in the woods with recursion
> (def! sumdown (fn* (N) (if (> N 0) (+ N (sumdown (- N 1))) 0)))
>
> As soon as you do
> (sumdown 1)
> you get an environment where N:1 and you got to calculate
> (+ N (sumdown (-N 1)))
> The first `N is not the problem, but
> now upon entering sumdown, the environment is restored/destroyed
> and N is nowhere to be seen.

The invocation of a closure has to mount the captured environment,
and then extend that environment with the parameters, which
are initializd with the argument values.

The captured environment doesn't have N, of course. N is freshly
bound each time the function is invoked.

This extension cannot mutate the original captured environment
because that is shared.

> The solution i found is the following.
> Case ...I is a weird exception. Exception! That is the keyword.
> So the idea is to evaluate (fn* (b) (+ a b))) 5) as if your nose bleeds,
> and then discover ERROR 8010 (symbol not found), for `a is not there.

This is not entirely related to the "N is nowhere to be seen" problem,
because N is a lambda argument, which a is not.

> Now you lift the not-found symbol `a from the stored environment to the
> inner environment and evaluate again.

The usual approach is to just chain all the necessary environments
in the correct order. They are searched in that order.

The "exception" is handled inline: we didn't find the symbol in
this environment, so we continue with the parent environment
in the chain.

(Then there are flattening optimizations to reduce the search;
e.g. when a lexical closure captures a bunch of nested environments,
it's possible to flatten them into one level.)

> Coming back to ... I
> A weird situation arises if in the meantime a function is called that
> has a separate and distinct `a (free) in the environment it was
> created in. Let's hope this doesn't happen.

You seem to be sayhing, let's not bother implementing lexical closures,
and pray that the application isn't relying on them?

It seems to me you might be doing this:

1. if the evaluation of the function runs into a free variable,
an "exception" occurs.

2. The exception is "handled" by searching for the variable in
the calling function's environment.

That amounts to dynamic scope, not lexical scope.

(let ((a 3))
(define fun ()
a))

(let ((a 4))
(fun)) -> 4

Here, fun has not actually captured any environment. When (fun) is
invoked, a is not found. This triggers an "exception" which is handled
by finding the (a 4) binding in the environment that is valid at the
time of the call.

This is called dynamic scope, not lexical.

Old Lisp is like this: MacCarthy's LISP 1, LISP 1.5.

Emacs Lisp used to be, but now supports lexical scoping on a per-file
basis. You can declare that lexical scope is used and the code will
be compiled accordingly.

Scheme first introduced lexical scope into the Lisp world.

To implement dynamic scope, you don't need any environments other
than the global namespace. When a variable is bound (by let, or
as a function parameter), the current value is saved somehwere,
like into the stack. When that scope terminates, the prior value
is restored.

Thus:

;; dynamic scope
(let ((a 4))
(fun)) -> 4

The a variable is assigned the value 4, after havving its prior value
saved. The (fun) call takes place, and sees 4. Then the let
terminates, restoring whatever was the prior value of a.

> [Why bother, people who write such programs had it coming.
> The least they have to do is to rename `a to
> TheDelayInMSBeforeDrawingTheBottomLineInaPurpleCaptionBox
> diminishing the risk for a name clash.]

Programs with escaping closures are written all the time. Not just in
Lisp, but in Javascript, Python and other languages.

It's become and indispensable feature.

The problem is not solved by renaming.

Yes, under dynamic scoping you have to use namespacing or renaming to
avoid accidental clashes between truly global variables and locals.

This is why you see the "earmuffs" notation in Lisps that are
dynamically scoped or support dynamic scope optionally.
Earmuffs notation means starting and ending a symbol name with *,
like *standard-output*, or *print-circle*.

Under dynamic scope, if a local variable has the same name as a global
variable by accident and then functions are called which rely on the
global variable, they will mistakenly be working with the local
variable.

(Under the saving-restoring implementation I outlined above, there are
not separate variables. But the local variable imposes its own value and
then restores the previous one, which interferes with the functions
relying on the global semantics.)

Renaming to avoid bugs due to clashes not give you the lexical closure
semantics, because you're not capturing the instance of the variable,
only the name.

The same lexical variable takes on new bindings with new invocations
of its lexical scope. A closure captures the specific binding of an
activation of the scope.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

### none albert

Aug 19, 2023, 2:32:29â€¯PM8/19/23
to
In article <202308190...@kylheku.com>,
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
>> https://github.com/kanaka/mal/
>>
>> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>
>> I run in a bit of trouble in the interaction between closures and recursion.
>>
>> I succeeded in handling closure in
>> ( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
>> In lisp we have
>> (fn* (fn* (b) (+ a b))) 5)
> ^ ^
<SNIP>
>The same lexical variable takes on new bindings with new invocations
>of its lexical scope. A closure captures the specific binding of an
>activation of the scope.

Thanks a lot for precisely answering a question that I brought
rather provocatively,[but I don't really thought renaming `a to a
really long name was a serious solution. ]
I have to study this to take in.

>--
>Mastodon: @Kazi...@mstdn.ca

### none albert

Aug 20, 2023, 8:25:16â€¯AM8/20/23
to
In article <202308190...@kylheku.com>,
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
>> https://github.com/kanaka/mal/
>>
>> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>
>> I run in a bit of trouble in the interaction between closures and recursion.
>>
<SNIP>
>
>The invocation of a closure has to mount the captured environment,
>and then extend that environment with the parameters, which
>are initializd with the argument values.

This puzzles me. That means that a function body can not refer
to data in the current environment only to data in the captured
environment.

>
>The captured environment doesn't have N, of course. N is freshly
>bound each time the function is invoked.
Mal implements the binding by defining a nested environment where N
is bound. So in my implementation of each recursive invocation of
the function destroys the previous binding.
This is exactly the problem.
>
>This extension cannot mutate the original captured environment
>because that is shared.
Clarokay. The original environment is not the problem.

>
>> The solution i found is the following.
>> Case ...I is a weird exception. Exception! That is the keyword.
>> So the idea is to evaluate (fn* (b) (+ a b))) 5) as if your nose bleeds,
>> and then discover ERROR 8010 (symbol not found), for `a is not there.
>
>This is not entirely related to the "N is nowhere to be seen" problem,
>because N is a lambda argument, which a is not.
>
>> Now you lift the not-found symbol `a from the stored environment to the
>> inner environment and evaluate again.
>
>The usual approach is to just chain all the necessary environments
>in the correct order. They are searched in that order.
>
>The "exception" is handled inline: we didn't find the symbol in
>this environment, so we continue with the parent environment
>in the chain.
You and MAL suggests that one can get by with one chain.
What is then this correct order?
Is that by any chance
outer original environment
{optional others}
* captured environment,
* environment that contains the parameter bindings.
In a recursive call the last two repeat.
>
>(Then there are flattening optimizations to reduce the search;
>e.g. when a lexical closure captures a bunch of nested environments,
>it's possible to flatten them into one level.)
>
>> Coming back to ... I
>> A weird situation arises if in the meantime a function is called that
>> has a separate and distinct `a (free) in the environment it was
>> created in. Let's hope this doesn't happen.
>
>You seem to be sayhing, let's not bother implementing lexical closures,
>and pray that the application isn't relying on them?
>
>It seems to me you might be doing this:
>
>1. if the evaluation of the function runs into a free variable,
> an "exception" occurs.
>
>2. The exception is "handled" by searching for the variable in
> the calling function's environment.
>
>That amounts to dynamic scope, not lexical scope.
I fear that it is worse, a mix of the two.
>
> (let ((a 3))
> (define fun ()
> a))
>
> (let ((a 4)) ...II
> (fun)) -> 4

If I understand it correctly,
MAL is talking about capturing the environment
so MAL is aiming at lexical scope
so if the test marked .. II gives the result specified,
then I have failed at implementing (this aspect of) MAL.

>
>Here, fun has not actually captured any environment. When (fun) is
>invoked, a is not found. This triggers an "exception" which is handled
>by finding the (a 4) binding in the environment that is valid at the
>time of the call.
>
>This is called dynamic scope, not lexical.
>
>Old Lisp is like this: MacCarthy's LISP 1, LISP 1.5.

I studied a lisp in Forth. There was only one scope, and
it looked like a lazy easy implementation.
I snipped the description you gave of these kind of
implementations.
It is here
https://github.com/albertvanderhorst/forthlisp
<SNIP>
>
>> [Why bother, people who write such programs had it coming.
>> The least they have to do is to rename `a to
>> TheDelayInMSBeforeDrawingTheBottomLineInaPurpleCaptionBox
>> diminishing the risk for a name clash.]
>
>Programs with escaping closures are written all the time. Not just in
>Lisp, but in Javascript, Python and other languages.

Of course you are right. But I prefer language where the compiler
instantiates the occurances of a, so that there are no confusion.

>It's become and indispensable feature.
>
>The problem is not solved by renaming.
Not solved but at least mitigated.

>Yes, under dynamic scoping you have to use namespacing or renaming to
>avoid accidental clashes between truly global variables and locals.
This is the familiar problem in C, where a global variable `i is
declared, and you run into problems using `i in local loops without
AMDX86 ciforth 5.4.0
CREATE DROP
>>>>>>>>>>> DROP : ISN'T UNIQUE <<<<<<<<<<<<<<<<<<<<
<SNIP>
>
>Mastodon: @Kazi...@mstdn.ca

### Spiros Bousbouras

Aug 20, 2023, 10:09:09â€¯AM8/20/23
to
On Sun, 20 Aug 2023 14:25:10 +0200
albert@cherry.(none) (albert) wrote:
> In article <202308190...@kylheku.com>,
> Kaz Kylheku <864-11...@kylheku.com> wrote:
> >On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
> >> https://github.com/kanaka/mal/
> >>
> >> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
> >>
> >> I run in a bit of trouble in the interaction between closures and recursion.
> >>
> <SNIP>
> >
> >The invocation of a closure has to mount the captured environment,
> >and then extend that environment with the parameters, which
> >are initializd with the argument values.
>
> This puzzles me. That means that a function body can not refer
> to data in the current environment only to data in the captured
> environment.

I don't know how you concluded that. Of course the function body can
refer to data in the current environment. You shouldn't read too
much in the order Kaz mentions the operations.

> >The usual approach is to just chain all the necessary environments
> >in the correct order. They are searched in that order.
> >
> >The "exception" is handled inline: we didn't find the symbol in
> >this environment, so we continue with the parent environment
> >in the chain.
> You and MAL suggests that one can get by with one chain.
> What is then this correct order?
> Is that by any chance
> outer original environment
> {optional others}
> * captured environment,
> * environment that contains the parameter bindings.

Correct order to do what ? If you mean look up then no. The usual
semantics is that the look up starts with the innermost environment
and then to ones further out and in lexical scoping what is innermost
means lexically i.e. syntactically.

(let ((a 1))
(defun foo (a)
[References to a are to the innermost one i.e. to the one which
was passed as argument to foo ] ))

> I studied a lisp in Forth. There was only one scope, and
> it looked like a lazy easy implementation.
> I snipped the description you gave of these kind of
> implementations.
> It is here
> https://github.com/albertvanderhorst/forthlisp

Why not study Lisp directly ? Closures are not rocket science , as
Kaz has pointed out. Speaking more generally , first you need to
understand what it is you are trying to implement and then implement
it , in Forth or any other language.

A binding is an association between a name and storage space. This applies
also to languages which don't support closures like C. An environment is a
collection (list , vector , whatever data structure you choose to implement
it) of bindings. Lets say your function has local variables A , B , C and
lets assume for simplicity that the value of each needs 4 bytes to be stored.
Then you might decide that the storage space for A is at the beginning of the
environment area , the storage space for B 4 bytes after that and the storage
space for C 8 bytes after that. If you were implementing a language without
closures then likely the environment would be where the stack pointer
(register) points on entry to the function. If you want closures , this isn't
good enough because the stack pointer will be restored to an earlier value
when the function exits. So in a language with closures , you can imagine
that each function gets passed behind the scenes (i.e. without an explicit
mention in the source code) a pointer to a linked list of environments or
perhaps a vector of environments where the first element of the linked list
or vector is the lexically innermost environment and additional elements are
moving outwards.

--
He wears a frock he loves the cock,
he sells his arse on Albert Dock
Football song referring to Fernando Torres

### Ben Bacarisse

Aug 20, 2023, 10:31:32â€¯AM8/20/23
to
albert@cherry.(none) (albert) writes:

> In article <202308190...@kylheku.com>,
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
>>> https://github.com/kanaka/mal/
>>>
>>> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>>
>>> I run in a bit of trouble in the interaction between closures and recursion.
>>>
> <SNIP>
>>
>>The invocation of a closure has to mount the captured environment,
>>and then extend that environment with the parameters, which
>>are initializd with the argument values.
>
> This puzzles me. That means that a function body can not refer
> to data in the current environment only to data in the captured
> environment.

You may be getting confused by using the term "current environment".
What is it you think the body of a function should be able to access
which is ruled out by the paragraph you quote? Can you give an example
so we can know more about what is puzzling you.

Look at the second part of the sentence. The function body is evaluated
in an environment that is built by extending the captured environment
with the bound function parameters.

When the closure is /created/, it captures the environment it is
evaluated in (what else it there?) but when it is subsequently /called/,
the function's parameters must be bound. That makes a new extended
environment based on the captured one. It is in this extended
environment that the body is evaluated.

--
Ben.

### Kaz Kylheku

Aug 20, 2023, 2:23:05â€¯PM8/20/23
to
On 2023-08-20, albert@cherry.(none) (albert) <albert@cherry> wrote:
> In article <202308190...@kylheku.com>,
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-08-19, albert@cherry.(none) (albert) <albert@cherry> wrote:
>>> https://github.com/kanaka/mal/
>>>
>>> I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>>
>>> I run in a bit of trouble in the interaction between closures and recursion.
>>>
><SNIP>
>>
>>The invocation of a closure has to mount the captured environment,
>>and then extend that environment with the parameters, which
>>are initializd with the argument values.
>
> This puzzles me. That means that a function body can not refer
> to data in the current environment only to data in the captured
> environment.

If functions can see bindings in the caller, then you have dynamic
scope.

Under dynamic scope, there are no closures. A lambda operator doesn't
capture anything; it just produces a code object that always executes in
whatever environment it finds itself in.

It's possible to have "dynamic closures" under dynamic scope.

21 years ago I made a dialect like that. Functions could see the parent
environment, but there were also closures that really captured.

I had it such that closures captured only the "lexical portion
of the dynamic environment" so to speak. How that worked is that
my environment chain contained invisible markers delimiting
lexical scopes. Each time a function was called, such a marker
was included in its parameter-argument binding environment frame.

Thus dynamic closures mimiced lexical scoping by capturing frames
up to the marker.

When a closure was invoked, the captured frames were inserted
ahead of the current dynamic environment.

It was kind of fun program in the dialect and worked well for
the purpose. The dialect connected to various C APIs and was used for
testing them. It also supported threading. It was possible to have tests
customized by various dynamic variables, and easily run a thread
with custom values of those variables:

(let ((*test-param-x* ...)
(*test-param-y* ...)
...)
(create-thread (lambda () ... (do-foo-test))))

The parmeter are dynamic: we are not passing them as parameters
to do-foo-test. Yet, because the "dynamic closure" mechanism,
the lambda will capture the values given in the let, and make
those values visible to (do-foo-test), which pure dynamic scope
would not do.

>>The usual approach is to just chain all the necessary environments
>>in the correct order. They are searched in that order.
>>
>>The "exception" is handled inline: we didn't find the symbol in
>>this environment, so we continue with the parent environment
>>in the chain.
> You and MAL suggests that one can get by with one chain.
> What is then this correct order?
> Is that by any chance
> outer original environment
> {optional others}
> * captured environment,
> * environment that contains the parameter bindings.
> In a recursive call the last two repeat.

Under pure lexical scope with not support for any kind of dynamic
scoping features, you don't have multiple chains spliced together.

Although I wrote about "chaining" in the right order what I should
have written is about environment extension.

When a function is invoked, it gets only its captured environment.
There is no other environment; it doesn't see anything else.

That environment is extended when nested variable-binding
constructs are evaluated. First the function parameters go on
top, then any nested let variables and soon.

Extending a shared environment is done without mutating the environment:
a new frame is pushed which points to that environment's hitherto top
frame. That frame becomes the new top (stack discipline). Contexts
working with the previous stack have the old pointer and don't see that.

The environment extensions are all new frames.

Outside of the lambda, the environment is the captured, shared
one. The interior environment is newly pushed. That's it.

So you can do it with one chain, if by that you mean one chain
per function activation. Each function call starts its own
environment chain, starting with the captured one and extending
from there.

> If I understand it correctly,
> MAL is talking about capturing the environment
> so MAL is aiming at lexical scope
> so if the test marked .. II gives the result specified,
> then I have failed at implementing (this aspect of) MAL.

I suspect yes, Mal is about lexical scope and not some exotic
blend of lexical and dynamic.

>>Programs with escaping closures are written all the time. Not just in
>>Lisp, but in Javascript, Python and other languages.
>
> Of course you are right. But I prefer language where the compiler
> instantiates the occurances of a, so that there are no confusion.

If a compiler can instantiate one occurence of a, that must be
a global variable. No compiler since Algol instantiates local
variables. However, compilers for lexical scopes can allocate
a local variablein a fixed frame location.

This is particularly simple in lexically scoped languages without
lexical closures.

For instance, in C, when a function is invoked, just the stack/frame
pointers have to be moved to create space for all the variables in
all the lexical scopes in that function flatted into one block,
in which all the variables ahve fixed offsets relative to the frame
pointer.

>
>>It's become and indispensable feature.
>>
>>The problem is not solved by renaming.
> Not solved but at least mitigated.
>
>>Yes, under dynamic scoping you have to use namespacing or renaming to
>>avoid accidental clashes between truly global variables and locals.
> This is the familiar problem in C, where a global variable `i is
> declared, and you run into problems using `i in local loops without
> a shadowing declaration.

That's because the shadowing declaration is a definition, and C
has lexical scope.

Under dynamic scope, a shadowing binding made by let is just overriding
the value of the global. To write code safely, you must do two
things:

- put global and locals into separate namespaces, e.g.
*var* and var.

- in every function, make sure you bind each local with let.
If you forget, you could be trashing a local variable of
you caller, whereas if you bind, you're correctly saving
and restoring the parent's variable.

### Kaz Kylheku

Aug 20, 2023, 2:35:57â€¯PM8/20/23
to
On 2023-08-20, Kaz Kylheku <864-11...@kylheku.com> wrote:
> If a compiler can instantiate one occurence of a, that must be
> a global variable. No compiler since Algol instantiates local
> variables. However, compilers for lexical scopes can allocate
> a local variablein a fixed frame location.
>
> This is particularly simple in lexically scoped languages without
> lexical closures.
>
> For instance, in C, when a function is invoked, just the stack/frame
> pointers have to be moved to create space for all the variables in
> all the lexical scopes in that function flatted into one block,
> in which all the variables ahve fixed offsets relative to the frame
> pointer.

Also note that lexical variables are subject to optimizations
(in compiler Lisps and Algogl-like languages alike).

Locals can be put into registers, over part of their lifetime
or even all of it.

Locals which are bound to constants and never assigned another
value are subject to constant propagation/folding, such that
they disappear.

Unused locals can simply disappear.

These optimizations are part of the motivation for lexical scope
being the way it is.

If a child function (particularly one in an other file or compilation
unit) could "see" the local variables in a parent, most of thse
optimizations would not be possible.

In C, and similar languages, you can pass the adddress of a local into
another function. When you do that, optimizations like the above
are entirely or partially defeated. If the variable lives in a
register, it has to be "spilled" into the backing memory location,
and reloaded from it after a function is called, due to the suspicion
that since other parts of the program know the variable's location,
they need that location to have the up-to-date value, and if the
variable is mutable, they might be messing with the content, so then
the original function needs to sample the up-to-date value.

### none albert

Aug 22, 2023, 4:08:38â€¯AM8/22/23
to
In article <nnd\$108a8f87\$6cca2ba5@1b35385dda51f7cd>,
none) (albert <albert@cherry.> wrote:
>https://github.com/kanaka/mal/
>
>I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>
>I run in a bit of trouble in the interaction between closures and recursion.
>
>( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
>In lisp we have
>(fn* (fn* (b) (+ a b))) 5)
>
>(def! sumdown (fn* (N) (if (> N 0) (+ N (sumdown (- N 1))) 0))) ...I

The above now passes the test of MAL.
This is what I do.
Assuming MAL is intended to be lexical, first look up symbols
in the parameter mapping,
then in the environment stored in the
closure, then in the environment where the call is made.
All environments can recursively refer to outer environments,
not the parameter mapping.

### Kaz Kylheku

Aug 22, 2023, 12:56:15â€¯PM8/22/23
to
On 2023-08-22, albert@cherry.(none) (albert) <albert@cherry> wrote:
> In article <nnd\$108a8f87\$6cca2ba5@1b35385dda51f7cd>,
> none) (albert <albert@cherry.> wrote:
>>https://github.com/kanaka/mal/
>>
>>I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>
>>I run in a bit of trouble in the interaction between closures and recursion.
>>
>>( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
>>In lisp we have
>>(fn* (fn* (b) (+ a b))) 5)
>>
>>(def! sumdown (fn* (N) (if (> N 0) (+ N (sumdown (- N 1))) 0))) ...I
>
> The above now passes the test of MAL.
> This is what I do.
> Assuming MAL is intended to be lexical, first look up symbols
> in the parameter mapping,
> then in the environment stored in the
> closure, then in the environment where the call is made.
> All environments can recursively refer to outer environments,
> not the parameter mapping.

If "environment where the call is made" in the last step there
refers to the lexical environment within the calling function,
you have a mistake.

Under lexical scope, an invoked function must not see variables
in the caller.

If an identifier is not found in the lexical scope, you can have a
fallback on a pervasive scope (for finding global variables).

If you're seeing locals in parent functions, you have dynamic
scope; and if taht is combined with closures that capture
environments, you have something that can be called "dynamic closurees".

It's a valid implementation choice; it's just not to be confused with
lexical scope.

If you have dynamic closures, then some test cases for lexical scope
will pass.

What will not pass are tests which tests for these things:

- error checking: validate that a free variable references
in a function which has the same name as a local variable
in a caller is diagnosed as an undefined reference,
rather than referring to the parent.

- interference: validate that if a callee assigns to a variable
x which happens to be a local variable in the caller,
it doesn't clobber the caller's variable.

Part of the motivation for lexical scope is encapsulation.
All accesses to a lexical variable are possible only from
the scope where it is visible, and nowhere else.

### none albert

Aug 23, 2023, 6:18:30â€¯AM8/23/23
to
In article <202308220...@kylheku.com>,
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-08-22, albert@cherry.(none) (albert) <albert@cherry> wrote:
>> In article <nnd\$108a8f87\$6cca2ba5@1b35385dda51f7cd>,
>> none) (albert <albert@cherry.> wrote:
>>>https://github.com/kanaka/mal/
>>>
>>>I'm trying to Make Another Lisp using ciforth lina/wina/xina.
>>>
>>>I run in a bit of trouble in the interaction between closures and recursion.
>>>
>>>( ( (fn* (a) (fn* (fn* (b) (+ a b))) 5) 7) ... I
>>>In lisp we have
>>>(fn* (fn* (b) (+ a b))) 5)
>>>
>>>(def! sumdown (fn* (N) (if (> N 0) (+ N (sumdown (- N 1))) 0))) ...I
>>
>> The above now passes the test of MAL.
>> This is what I do.
>> Assuming MAL is intended to be lexical, first look up symbols
>> in the parameter mapping,
>> then in the environment stored in the
>> closure, then in the environment where the call is made.
>> All environments can recursively refer to outer environments,
>> not the parameter mapping.
>
>If "environment where the call is made" in the last step there
>refers to the lexical environment within the calling function,
>you have a mistake.
>
>Under lexical scope, an invoked function must not see variables
>in the caller.

Thank you for clearing that up. The git site is guiding you
through implementation but is short of background.

>
>If an identifier is not found in the lexical scope, you can have a
>fallback on a pervasive scope (for finding global variables).

I assume that functions as + * / etc are present in this
pervasive scope. That makes sense and it is much easier
to implement.
>
>If you're seeing locals in parent functions, you have dynamic
>scope; and if taht is combined with closures that capture
>environments, you have something that can be called "dynamic closurees".
>
>It's a valid implementation choice; it's just not to be confused with
>lexical scope.

>
>If you have dynamic closures, then some test cases for lexical scope
>will pass.
>
>What will not pass are tests which tests for these things:
>
>- error checking: validate that a free variable references
> in a function which has the same name as a local variable
> in a caller is diagnosed as an undefined reference,
> rather than referring to the parent.
>
>- interference: validate that if a callee assigns to a variable
> x which happens to be a local variable in the caller,
> it doesn't clobber the caller's variable.

I'm adding to the mal tests. These are test are candidates.

>
>Part of the motivation for lexical scope is encapsulation.
>All accesses to a lexical variable are possible only from
>the scope where it is visible, and nowhere else.

Tanks for clearing that up. As MAL is supposed to be a Clojure
derivative, I will simply following the lexical closure paradigm.
This clears up some remarks I found puzzling in the MAL git
site about tail call optimisation.

>Mastodon: @Kazi...@mstdn.ca

### none albert

Aug 26, 2023, 8:50:05â€¯AM8/26/23
to
In article <202308190...@kylheku.com>,
Kaz Kylheku <864-11...@kylheku.com> wrote:
<SNIP>
>It seems to me you might be doing this:
>
>1. if the evaluation of the function runs into a free variable,
> an "exception" occurs.
>
>2. The exception is "handled" by searching for the variable in
> the calling function's environment.
>
>That amounts to dynamic scope, not lexical scope.
>
> (let ((a 3))
> (define fun ()
> a))
>
> (let ((a 4))
> (fun)) -> 4
>
>Here, fun has not actually captured any environment. When (fun) is
>invoked, a is not found. This triggers an "exception" which is handled
>by finding the (a 4) binding in the environment that is valid at the
>time of the call.
>
I tested it, and my implementation fails the dynamic scope test.
But what is supposed to happen if `a is global (pervasive environment)
here?

(define a 12)
(define fun () a)
(define a 13)
(fun)

If the answer should be 12 , it seems to me that to accommodate this a
possibly infinite number of snapshots of the global environment should
exist.
Maybe I have a too much algol mindset. A recursive `i in a Fibonacci recursion
refer to different instances, mentally labeled as fib<12>.fib<11>...fib<1>.i.

I have README's in different directories. I don't identify those, but I could.
There is a list of filenames, and as soon as I change directory the i-node of
the README in this directory is filled in in the list.
Is this the way the name `a is handled?

>Mastodon: @Kazi...@mstdn.ca

### Kaz Kylheku

Aug 27, 2023, 1:45:45â€¯AM8/27/23
to
On 2023-08-26, albert@cherry.(none) (albert) <albert@cherry> wrote:
> I tested it, and my implementation fails the dynamic scope test.
> But what is supposed to happen if `a is global (pervasive environment)
> here?
>
> (define a 12)
> (define fun () a)
> (define a 13)
> (fun)

If there is a top-level environment like in Common Lisp, then the
second definition of a is actually an assignment.

If there is a top-level lexical scope, then the second a is a new
lexical identifier unrelated to the first a, and so fun refers
to the 12 not the 13.

This is a just a matter of knowing the requirements in MAL.

> I have README's in different directories. I don't identify those, but I could.
> There is a list of filenames, and as soon as I change directory the i-node of
> the README in this directory is filled in in the list.
> Is this the way the name `a is handled?

The static view of the lexical scope, like what a compiler or any other code
walker sees can be compared to directory structure, if we imagine a directory
structure in which subdirectories point to their parents, but parents don't
know about the subdirectories.

The syntax of the program references scopes, and those scopes have parent
scopes.

Lexical scopes are blueprints for something that happens at run-time;
there isn't anything comparaible in file system directories.

If everytime we step into a directory, we got a new empty one in which
there are freshly created files that are either empty or have some specific
initial contents, ... maybe that would resemble scopes.

### none albert

Aug 27, 2023, 7:12:52â€¯AM8/27/23
to
In article <202308261...@kylheku.com>,
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-08-26, albert@cherry.(none) (albert) <albert@cherry> wrote:
>> I tested it, and my implementation fails the dynamic scope test.
>> But what is supposed to happen if `a is global (pervasive environment)
>> here?
>>
>> (define a 12)
>> (define fun () a)
>> (define a 13)
>> (fun)
>
>If there is a top-level environment like in Common Lisp, then the
>second definition of a is actually an assignment.
>
>If there is a top-level lexical scope, then the second a is a new
>lexical identifier unrelated to the first a, and so fun refers
>to the 12 not the 13.
>
>This is a just a matter of knowing the requirements in MAL.

That is far as you can help me. Unfortunately there is no
requirements for MAL, only an implementation model.
The descriptions are very lispy, and my implementation language
is totally different. But that was the point of this exercise
anyway. Thanks anyway.

I like the explanation of lisp concepts on this website "lisp from
nothing", but it is not much help in implementing them.
https://www.t3x.org/lfn/index.html

### Spiros Bousbouras

Aug 27, 2023, 8:45:44â€¯AM8/27/23
to
On Sun, 27 Aug 2023 13:12:40 +0200
albert@cherry.(none) (albert) wrote:
> In article <202308261...@kylheku.com>,
> Kaz Kylheku <864-11...@kylheku.com> wrote:
> >This is a just a matter of knowing the requirements in MAL.
>
> That is far as you can help me. Unfortunately there is no
> requirements for MAL, only an implementation model.
> The descriptions are very lispy, and my implementation language
> is totally different. But that was the point of this exercise
> anyway. Thanks anyway.

If you don't have requirements then use your programmer's instinct.
If you were to use the Lisp you are implementing for writing useful
programmes , which behaviour would you find most useful ? Then
implement that behaviour.

> I like the explanation of lisp concepts on this website "lisp from
> nothing", but it is not much help in implementing them.
> https://www.t3x.org/lfn/index.html

The website has code. Unless you mean it's not much help in implementing
them in Forth. I think https://letoverlambda.com/textmode.cl/guest/toc
has a Lisp implemented in Forth but what's online doesn't make it clear.
You could buy the book.

--
A goatscape (not to be confused with "scapegoat") is a landscape full of goats.

### none albert

Aug 31, 2023, 5:37:57â€¯AM8/31/23
to
In article <e1jFR1e0...@bongo-ra.co>,
Spiros Bousbouras <spi...@gmail.com> wrote:
>On Sun, 27 Aug 2023 13:12:40 +0200
>albert@cherry.(none) (albert) wrote:
>> In article <202308261...@kylheku.com>,
>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>> >This is a just a matter of knowing the requirements in MAL.
>>
>> That is far as you can help me. Unfortunately there is no
>> requirements for MAL, only an implementation model.
>> The descriptions are very lispy, and my implementation language
>> is totally different. But that was the point of this exercise
>> anyway. Thanks anyway.
>
>If you don't have requirements then use your programmer's instinct.
>If you were to use the Lisp you are implementing for writing useful
>programmes , which behaviour would you find most useful ? Then
>implement that behaviour.

I have no requirements for lisp. The MAL challenge is not to
implement a lisp, but use a particular language (Forth FORTRAN C
python go list-this lisp-that) to investigate the strong and weak
side of the implementation language for implementing it.
The attraction of the MAL side is that it has step-by-step
test driven development. Skipping MAL features is just cheating.

The strong point in my Forth implementation is the parser, that
is way simpler than any other implementation's parser.
I'm on my way to spend approximately 30% of the code compared
to the Forth that is already present in MAL.

>
>> I like the explanation of lisp concepts on this website "lisp from
>> nothing", but it is not much help in implementing them.
>> https://www.t3x.org/lfn/index.html
>
>The website has code. Unless you mean it's not much help in implementing
>them in Forth. I think https://letoverlambda.com/textmode.cl/guest/toc
>has a Lisp implemented in Forth but what's online doesn't make it clear.
I have done a lisp in Forth
https://github.com/albertvanderhorst/forthlisp

>You could buy the book.
Considering it. It is interesting in his own right.

I once worked through a lisp course book, so I have a basic skill.
From the 400 plus problems I have solved from projecteuler.net the
great majority were amenable to Forth. A few problems were easier in
Python, prolog or c. At no time I have felt inspired to use lisp.

### Spiros Bousbouras

Aug 31, 2023, 3:04:25â€¯PM8/31/23
to
On Thu, 31 Aug 2023 11:37:50 +0200
albert@cherry.(none) (albert) wrote:
> In article <e1jFR1e0...@bongo-ra.co>,

[...]

> I have no requirements for lisp. The MAL challenge is not to
> implement a lisp, but use a particular language (Forth FORTRAN C
> python go list-this lisp-that) to investigate the strong and weak
> side of the implementation language for implementing it.
> The attraction of the MAL side is that it has step-by-step
> test driven development. Skipping MAL features is just cheating.

[...]

> I have done a lisp in Forth
> https://github.com/albertvanderhorst/forthlisp

Then what's the point of doing MAL ? Just to compare your code with that
by other people in other languages ?

### none albert

Sep 1, 2023, 9:01:11â€¯AM9/1/23
to
In article <prm+jxSU...@bongo-ra.co>,
That is correct. The challenge is to build MAL using
as many languages you can think of.

The languages are:
ada awk bash basic c chuck clojure coffee common-lisp cpp crystal cs d
dart docs elisp elixir elm erlang es6 examples factor fantom forth
fsharp gnu-smalltalk go groovy guile haskell haxe hy io java js julia
kotlin livescript logo lua make mal matlab miniMAL nasm nim objc
objpascal ocaml perl perl6 php picolisp plpgsql plsql powershell
process ps python r racket rexx rpython ruby rust scala scheme skew
swift swift3 swift4 tcl ts vb vhdl vimscript wasm yorick

Obviously a lisp in vimscript or make or bash, are an implementation
challenge rather than an attempt to make usable lisp.
It is the intent to start from scratch, use idiomatic solutions for
your language and look as little to other implementations as possible.

My goal is to gain experience using Forth to implement other languages.
Also implementing a language gives a different perspective that
merely using the language.
Forth programming is extending the language Forth. I had no need to
define a class, structure or object for implementing MAL,
only using constructs that are present in Forth itself.
E.g. building a list is creating a Forth header, and filling in the
tag and the data field:
: build-list #list LHEADER >R R@ >DFA ! R> ;
Binding an object to a name in an environment is
: set >R \$, 0 R@ >LFA ! R@ >NFA ! R> ENVIR @ LINK ;
Only #list and ENVIR are lisp-specific.
INTERPRET is the read evaluate loop of Forth and it is used to
read lisp code, admittedly tweaking token delimiters (Forth only
knows blank space as token delimiters.)
0 new messages