@MSGID: <20230819073816.564@kylheku.com> a0c46600
@REPLY:
7eb40bb2
@REPLYADDR Kaz Kylheku <864-117-4973@kylheku.com>
@REPLYTO 2:5075/128 Kaz Kylheku
@CHRS: CP866 2
@RFC: 1 0
@RFC-Message-ID: <20230819073816.564@kylheku.com>
@RFC-References:

@TZUTC: -0000
@PID: slrn/1.0.3 (Linux)
@TID: FIDOGATE-5.12-ge4e8b94
On 2023-08-19, albert@cherry.(none) (albert)  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: @Kazinator@mstdn.ca
--- slrn/1.0.3 (Linux)
 * Origin: A noiseless patient Spider (2:5075/128)
SEEN-BY: 5001/100 5015/255 5019/40 5020/715 848
1042 4441 12000 5030/49 1081
SEEN-BY: 5058/104 5075/128
@PATH: 5075/128 5020/1042 4441