Discussion:
How to implement lexical scoping?
(too old to reply)
luserdroog
2020-10-09 04:19:28 UTC
Permalink
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.

There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.

How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
Kaz Kylheku
2020-10-09 06:28:32 UTC
Permalink
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.

To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.

To evaluate something in a new lexical environment, you just push the
new bindings onto the assoc list that you were handed down as your own
environment, and then pass that new assoc list to the evaluator. Then
when that evaluation is done, throw that object away.

Making a closure is very simple: a two-field object containing the current
environment pointer (passed in as a parameter to the context where the
closure is being taken), and containg a reference to the code
part of the closure: the function parameters and body.

Calling a closure means: 1) retrieving the environment from the
closure object (e.g. assoc list), 2) binding the arguments (obtaining
the parameters from the closure, and pushing new bindings onto
the assoc list assocating those parameters with the argument values
and 3) evaluating the body of the function in the newly created
environment which has the parameter bindings.
--
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
Jeff Barnett
2020-10-09 07:03:19 UTC
Permalink
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
To evaluate something in a new lexical environment, you just push the
new bindings onto the assoc list that you were handed down as your own
environment, and then pass that new assoc list to the evaluator. Then
when that evaluation is done, throw that object away.
Making a closure is very simple: a two-field object containing the current
environment pointer (passed in as a parameter to the context where the
closure is being taken), and containg a reference to the code
part of the closure: the function parameters and body.
Calling a closure means: 1) retrieving the environment from the
closure object (e.g. assoc list), 2) binding the arguments (obtaining
the parameters from the closure, and pushing new bindings onto
the assoc list assocating those parameters with the argument values
and 3) evaluating the body of the function in the newly created
environment which has the parameter bindings.
If I'm reading the above correctly, there is a problem. Lexical scoping
behaves exactly like dynamic scoping except in two cases: 1) you recur
into an outer defined function or 2) you make a closure. In the first
case, the outer function, when reentered) sees none of the bindings done
by itself through those done by the inner function where the recursive
call occurs. The outer function when reentered will add its list of
bindings in the usual way.

The usual way to implement lexical scoping (in an interpreter) is to
make each binding primitive make a list of the binding cells created at
that level; when you recur downwards, you just add a list of the new
bindings to the binding list (a list of lists). When you recur, you take
off the proper number of binding lists (on that list of binding lists)
and start from there. A closure simply takes a function (an executable)
and pairs it with the current list of binding lists.

References to a lexical variable need two things: 1) B number of lexical
scopes backward where the binding exists and 2) N the name of the
variable. You take the list of binding lists and pass by the first B
binding lists then you take the top binding list (after the pass by) and
search for the binding of N in that list. If you don't want the bother
of determining B in advance (sort of like compiling), you can do an
assoc for N in the lists of bindings in the order they occur in the list
of lists. This may or may not be much slower depending on the cache
architecture of the machine hosting your interpreter.

You said many of the things I've said here some; you did not or said in
a way that confused me.
--
Jeff Barnett
Kaz Kylheku
2020-10-09 07:59:11 UTC
Permalink
Post by Jeff Barnett
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
To evaluate something in a new lexical environment, you just push the
new bindings onto the assoc list that you were handed down as your own
environment, and then pass that new assoc list to the evaluator. Then
when that evaluation is done, throw that object away.
Making a closure is very simple: a two-field object containing the current
environment pointer (passed in as a parameter to the context where the
closure is being taken), and containg a reference to the code
part of the closure: the function parameters and body.
Calling a closure means: 1) retrieving the environment from the
closure object (e.g. assoc list), 2) binding the arguments (obtaining
the parameters from the closure, and pushing new bindings onto
the assoc list assocating those parameters with the argument values
and 3) evaluating the body of the function in the newly created
environment which has the parameter bindings.
If I'm reading the above correctly, there is a problem. Lexical scoping
behaves exactly like dynamic scoping except in two cases: 1) you recur
into an outer defined function or 2) you make a closure. In the first
case, the outer function, when reentered) sees none of the bindings done
by itself through those done by the inner function where the recursive
call occurs. The outer function when reentered will add its list of
bindings in the usual way.
Under lexical scoping, we do not pass any environment across function
calls, period. When a function is processed by the interpreter, it
retrieves the captured lexical environment of that function and
works with that. The incoming lexical environment that the interpreter
received from its caller is ignored.

This can all be hidden in an "apply" function. I.e. a function call can
be processed by calling (apply <closure> <args>). That will fire up its
own nested interpreter session: no environment passing.

The environment is passed down and extended when interpreting nested
constructs in the same scope.
Zyni Moë
2020-10-09 09:37:08 UTC
Permalink
Post by Kaz Kylheku
Under lexical scoping, we do not pass any environment across function
calls, period. When a function is processed by the interpreter, it
retrieves the captured lexical environment of that function and
works with that. The incoming lexical environment that the interpreter
received from its caller is ignored.
Exactly this. If you use explicit environment then when interp does (apply
fn args env) then dynamic scope evaluates body of fn with that env extended
by fn's arg bindings, lexical scope simply discards env and uses env fn was
defined in instead, extended by fn's arg bindings again. Difference in
scoping rules can be controlled by single conditional in single place:
everything else is identical. Is really nice to write tiny metacircular
lisp this way.
--
the small snake
Jeff Barnett
2020-10-09 16:56:37 UTC
Permalink
Post by Kaz Kylheku
Post by Jeff Barnett
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
To evaluate something in a new lexical environment, you just push the
new bindings onto the assoc list that you were handed down as your own
environment, and then pass that new assoc list to the evaluator. Then
when that evaluation is done, throw that object away.
Making a closure is very simple: a two-field object containing the current
environment pointer (passed in as a parameter to the context where the
closure is being taken), and containg a reference to the code
part of the closure: the function parameters and body.
Calling a closure means: 1) retrieving the environment from the
closure object (e.g. assoc list), 2) binding the arguments (obtaining
the parameters from the closure, and pushing new bindings onto
the assoc list assocating those parameters with the argument values
and 3) evaluating the body of the function in the newly created
environment which has the parameter bindings.
If I'm reading the above correctly, there is a problem. Lexical scoping
behaves exactly like dynamic scoping except in two cases: 1) you recur
into an outer defined function or 2) you make a closure. In the first
case, the outer function, when reentered) sees none of the bindings done
by itself through those done by the inner function where the recursive
call occurs. The outer function when reentered will add its list of
bindings in the usual way.
Under lexical scoping, we do not pass any environment across function
calls, period. When a function is processed by the interpreter, it
retrieves the captured lexical environment of that function and
works with that. The incoming lexical environment that the interpreter
received from its caller is ignored.
I had hoped it would be obvious, but I was wrong it seems, that I'm
talking about calls among functions with definitions that are lexically
nested. In fact, the scheme I was describing was more or less what was
implemented on the Burrough's Algol machines. There were an ordered set
of hardware registers (the list of lists) called the "displays". Each
display register pointed at an ordered list of bindings. The above
described manipulations were done by the hardware as determined by their
compiler. It was also the model for many software implementations where
the inner binding list were not kept on a stack so it was much easier to
build upwards closures.
Post by Kaz Kylheku
This can all be hidden in an "apply" function. I.e. a function call can
be processed by calling (apply <closure> <args>). That will fire up its
own nested interpreter session: no environment passing.
The environment is passed down and extended when interpreting nested
constructs in the same scope.
You must do more than pass down the environment: you must PRUNE it when
recursively calling a function whose definition the call is nested in,
perhaps several function definitions deep.
--
Jeff Barnett
Kaz Kylheku
2020-10-09 21:43:39 UTC
Permalink
Post by Jeff Barnett
I had hoped it would be obvious, but I was wrong it seems, that I'm
talking about calls among functions with definitions that are lexically
nested. In fact, the scheme I was describing was more or less what was
implemented on the Burrough's Algol machines. There were an ordered set
of hardware registers (the list of lists) called the "displays". Each
display register pointed at an ordered list of bindings. The above
described manipulations were done by the hardware as determined by their
compiler.
My TXR Lisp impelments Algol-like displays. Lexical frames are vectors,
which are referenced by an array of pointers (the display vector).

The display vector always lives on the native stack.

The lexical frames are initially created on the stack also.
Post by Jeff Barnett
It was also the model for many software implementations where
the inner binding list were not kept on a stack so it was much easier to
build upwards closures.
This is exactly what I did. The binding frames always initially start
out on the stack. But when a lexical closure is made, they are relocated
into a heap object.

When a closure is invoked, a display is re-created, again on the native
stack, but stuffed with pointers to the heap-allocated frames.

This implementation has the advantage that:

1) We get stack-allocated locals for free: no complexity in the
compiler.

2) Lexical closures are often small, compared to the "flat closure"
strategy.

3) We get correct semantics of shared, mutated variables (variables
shared between multiple closures, and mutated by them) for free.

Basically the instruction set architecture of the virtual machine hides
the mechanism from programs, so the compiler is very simple.

Calls among functions that are nested in the same definition are
handled in the same way as all other calls. This makes them just as
slow, but correct. Regardless of who calls it, a function gets its own
execution environment with a newly initialized display, fabricated
according to the content of its closure and nothing else.
luserdroog
2020-10-09 16:42:37 UTC
Permalink
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
Ok. I'm partly doing this. But currently the global env is modified by
SET, SETQ, and DEFUN. So I guess these functions and functions that call
them will need modification to pass the env and return a modified one.
So I suppose getting rid of the global env is the first step.
Kaz Kylheku
2020-10-09 21:06:18 UTC
Permalink
Post by luserdroog
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
Ok. I'm partly doing this. But currently the global env is modified by
SET, SETQ, and DEFUN. So I guess these functions and functions that call
If you're interpreting a dynamically scoped Lisp using an interpreter
in Common Lisp, you might as well do one of two things. Given a form
like:

;; save and restore dynamic environment

(with-saved-dyn-env
(bind-dynamic-var ...)
(interpret-this-or-that))

We can:

1. Use unwind-protect to guard the restoration of the dynamic
environment, so the expansion is like this:

(let ((#:g025 %dyn-env%))
(progn (bind-dynamic-var ...)
(interpret-this-or-that))

(setf %dyn-env% #:g025))

2. Just use a special variable for the environment, so
we bootstrap the dynamic scope in the interpreted language
from that of the host language.

(let ((*dyn-env* *dyn-env*)) ;; save and restore
(bind-dynamic-var ...)
(interpret-this-or-that))

Dynamic scope has the virtue that it's easy for the host language's
dynamic scope to be used by the hosted language. You can just directly
use host language variables for the dynamic variables of the hosted
language.

Common Lisp has a special operator progv for binding dynamic variables,
which basically exists in supports of writing dynamically scoped
interpreters and related techniques.
Post by luserdroog
them will need modification to pass the env and return a modified one.
So I suppose getting rid of the global env is the first step.
Yes, and no.

Let me now describe a different implementation strategy.

Dynamnic scope can be made to behave like lexical scope, yet
retain the dynamism.

Firstly, let me say that even if you pass the environment around
everywhere and avoid the global variable, you can still have dynamic
scope. You can do that by making closures dumb (no environment stored in
them) and by passing the envrionment even into the function application
machinery, so that function bodies are evaluated in a scope which
includes the passed-down environment extended with the parameter
bindings (and not any closed environment).

About 17 years ago I wrote a dialect called VoqLisp (in C++) which
passed the environment around, but passed it into the function calling
machinery also. Functions could see the values of parent variables:

(let ((*foo* 42))
(fun)) ;; fun could see *foo*

Yet, lexical closures worked in this dialect.

How that worked was: each environment frame carried a "is-top-level"
flag. Whenever a function was called, the brand new environment
frame which was created for it, and pushed onto the environment
stack, had this flag set to true.

The lambda operator created a closure by taking a delimited slice of the
environment, up to and including the closest frame marked is-top-level.
It made a copy of this environment and stuck it into the closure.

The invocation of a lambda spliced the captured environment
onto the environment. So that is to say, a function would see its
parameter bindings first, the captured environment slice second,
and after that, the current dynamic scope.

(In retrospect, all of this is eerily similar to one of the possible
strategies of implementing delimited closures. My implementation was
doing with variable bindings what delimited closures do with the entire
control context.)

This scoping strategy came in quite handy in the application,
which was API testing on an embedded device.

Tests could be written which were governed by multiple parameters
represented as special variables.

Specific test cases could customize some of those variables
and then produce a closure, for instance:

(let ((*foo-param* foo-var)
(*bar-param* bar-var))
(make-thread (lambda () (frobozz-test))))

The above overrides two parameters. These overrides are captured
by the lambda, which is then the thread function for a new thread.
The thread runs (frobozz-test) which uses those values of
*foo-param* and *bar-param*, and the pervasive dynamic defaults
of all other parameters (which could be numerous).

When the lambda is invoked, the captured dynamic environment
slice containing the *foo-param* and *bar-param* bindings
is pushed on top of whatever dynamic environment is current.
Then the parameters are pushed (there aren't any in this case),
and then the body is evaluated.

You can't do this in exactly the above way with either lexical scope or
dynamic scope. With lexical + dynamic scope can do it like this:

(make-thread (lambda ()
(let ((*foo-param* foo-var)
(*foo-param* bar-var))
(frobozz-test)))

So though it may not look like a big deal, it's still neat how
you could host that binding outside of the lambda, and still
have it work.

For one thing, how it this was practically useful useful is that
multiple tests could share the parameters:


(let ((*foo-param* foo-var)
(*bar-param* bar-var))
(make-thread (lambda () (frobozz-test)))
(make-thread (lambda () (scrotelytest)))
...)

I.e. by being able to move the binding out of the lambda, we can share
it among multiple lambdas easily. This gave the code an intuitive
structure: the code could have a section where parameters are
established with let, wrapped around code that farms multiple tests
onto threads.
--
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
luserdroog
2020-10-10 03:38:35 UTC
Permalink
Post by Kaz Kylheku
Post by luserdroog
Post by Kaz Kylheku
Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
dynamic scoping.
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
Ok. I'm partly doing this. But currently the global env is modified by
SET, SETQ, and DEFUN. So I guess these functions and functions that call
If you're interpreting a dynamically scoped Lisp using an interpreter
in Common Lisp, you might as well do one of two things.
It's written in C actually. You've seen it before, some years ago.
In fact, the defun() macro I'm using was your idea.
https://github.com/luser-dr00g/sexp.c

I'm struggling to follow the rest of your post. I don't know enough
CL to really follow the examples. But I appreciate the effort. I'll
read it over several times and try to get something out of it.

It seems like I may also need to modify the way FSUBRs are called,
since they'll need an environment to work with.
Paul Rubin
2020-10-10 05:35:23 UTC
Permalink
Post by luserdroog
I'm struggling to follow the rest of your post. I don't know enough
CL to really follow the examples. But I appreciate the effort. I'll
read it over several times and try to get something out of it.
You should look at a Scheme implementation like Microscheme. Also if
you haven't read SICP, at least the chapter on metacirculat evaluators,
you probably should. It's at mitpress.mit.edu/sicp .
luserdroog
2020-10-11 01:42:28 UTC
Permalink
Post by Paul Rubin
Post by luserdroog
I'm struggling to follow the rest of your post. I don't know enough
CL to really follow the examples. But I appreciate the effort. I'll
read it over several times and try to get something out of it.
You should look at a Scheme implementation like Microscheme. Also if
you haven't read SICP, at least the chapter on metacirculat evaluators,
you probably should. It's at mitpress.mit.edu/sicp .
Thanks. I pulled it off of the shelf. Also Anatomy of Lisp.
I've heard good things about L.i.s.p. but never wanted to cough up
the money.
luserdroog
2020-10-11 02:19:48 UTC
Permalink
Post by luserdroog
Post by Paul Rubin
Post by luserdroog
I'm struggling to follow the rest of your post. I don't know enough
CL to really follow the examples. But I appreciate the effort. I'll
read it over several times and try to get something out of it.
You should look at a Scheme implementation like Microscheme. Also if
you haven't read SICP, at least the chapter on metacirculat evaluators,
you probably should. It's at mitpress.mit.edu/sicp .
Thanks. I pulled it off of the shelf. Also Anatomy of Lisp.
I've heard good things about L.i.s.p. but never wanted to cough up
the money.
What about Burge, /Recursive Programming Techniques/? Anything pertinent
in there? looks like "2.11 Sharing, Assignment, and Copying" might help.
Paul Rubin
2020-10-11 06:04:54 UTC
Permalink
Post by luserdroog
I've heard good things about L.i.s.p. but never wanted to cough up
the money.... What about Burge, /Recursive Programming Techniques/?
I'm not familiar with either of those, but I think SICP should be enough
to get you going. The Little Schemer has its own following so you might
check it out, but I myself have never understood it. If you can read C,
you might examine the source code of a simple Scheme implementation

SIOD is still quite small and has some implementation notes, but the
earlier even smaller version (1.0 or whatever) doesn't seem to be here:

http://people.delphiforums.com/gjc//siod.html

It is around if you look for it, or I can probably dig it up for you if
you want it.
Nils M Holm
2020-10-11 07:30:09 UTC
Permalink
Post by Paul Rubin
SIOD is still quite small and has some implementation notes, but the
Even smaller: https://t3x.org/klisp/index.html
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
luserdroog
2020-10-11 18:43:42 UTC
Permalink
Post by Nils M Holm
Post by Paul Rubin
SIOD is still quite small and has some implementation notes, but the
Even smaller: https://t3x.org/klisp/index.html
Very cool stuff. How do you get by without LABEL? Is SETQ simpler
to define as a Special Form than as a FSUBR?
Nils M Holm
2020-10-12 07:34:35 UTC
Permalink
Post by luserdroog
Post by Nils M Holm
Post by Paul Rubin
SIOD is still quite small and has some implementation notes, but the
Even smaller: https://t3x.org/klisp/index.html
Very cool stuff. How do you get by without LABEL?
There is LABELS in the LISP part of the interpreter (file klsrc).
Post by luserdroog
Is SETQ simpler
to define as a Special Form than as a FSUBR?
A special form can be wither an FEXPR or an FSUBR, so I am not sure
I understand your question! FWIW, SETQ is an FSUBR in Kilo LISP and
it is much easier to implement than LABELS. LABELS is a macro.
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
luserdroog
2020-10-12 07:52:22 UTC
Permalink
Post by Nils M Holm
Post by luserdroog
Post by Nils M Holm
Post by Paul Rubin
SIOD is still quite small and has some implementation notes, but the
Even smaller: https://t3x.org/klisp/index.html
Very cool stuff. How do you get by without LABEL?
There is LABELS in the LISP part of the interpreter (file klsrc).
Ok, I didn't see it in the manual. I guess the list of Special
Forms there isn't exhaustive.
Post by Nils M Holm
Post by luserdroog
Is SETQ simpler
to define as a Special Form than as a FSUBR?
A special form can be wither an FEXPR or an FSUBR, so I am not sure
I understand your question! FWIW, SETQ is an FSUBR in Kilo LISP and
it is much easier to implement than LABELS. LABELS is a macro.
Sorry, it was probably a stupid question. Much inspired, in any
case.
Nils M Holm
2020-10-12 10:05:25 UTC
Permalink
Post by luserdroog
Post by Nils M Holm
There is LABELS in the LISP part of the interpreter (file klsrc).
Ok, I didn't see it in the manual. I guess the list of Special
Forms there isn't exhaustive.
I see it on the first page of https://t3x.org/klisp/klisp.txt.html:

| [...] The following special forms exist:
|
| Core: APPLY IF IFNOT LAMBDA PROG QUOTE SETQ
| Derived: LET LABELS COND AND OR QQUOTE LOOP
^^^^^^
Post by luserdroog
Much inspired, in any case.
Good to hear!
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Paul Rubin
2020-10-12 00:38:52 UTC
Permalink
Post by Nils M Holm
Even smaller: https://t3x.org/klisp/index.html
This looks cute though I'm not sure how its size compares with early
SIOD. Lexical scope is maybe best implemented in a compiler (at least a
rudimentary one, like to a stack VM) rather than by direct
interpretation. It seems to me that the Hedgehog Lisp VM is a good
target for that sort of thing:

https://github.com/sbp/hedgehog

I have a joke that I want to use that VM as a target interpreter for a
microprocessor oriented subset of Haskell. I'm going to call it
Control-H, and the file extension will be a backspace character ;).

Unfortunately, Hedgehog's compiler is written in C. It's like the
author didn't believe in Hedgehog enough to use it for its own
compiler.

I think it should be possible to write a usable small Lisp or Scheme
system with no more than a few hundred lines of C or asm, for a low
level interpreter. The rest would be written in Lisp (or Scheme)
itself. Certainly the reader and printer should be written that way.
Nils M Holm
2020-10-12 07:31:23 UTC
Permalink
Post by Paul Rubin
Post by Nils M Holm
Even smaller: https://t3x.org/klisp/index.html
This looks cute though I'm not sure how its size compares with early
SIOD.
The earliest SIOD I remember was almost twice as big as Kilo LISP.
Post by Paul Rubin
Lexical scope is maybe best implemented in a compiler (at least a
rudimentary one, like to a stack VM) rather than by direct
interpretation.
I agree that it is best implemented *efficiently* in a compiler. It
is very easy to implement when using deep binding in an interpreter.
Post by Paul Rubin
I have a joke that I want to use that VM as a target interpreter for a
microprocessor oriented subset of Haskell. I'm going to call it
Control-H, and the file extension will be a backspace character ;).
:)
Post by Paul Rubin
I think it should be possible to write a usable small Lisp or Scheme
system with no more than a few hundred lines of C or asm, for a low
level interpreter. The rest would be written in Lisp (or Scheme)
itself. Certainly the reader and printer should be written that way.
My upcoming book shows an implementation of a self-hosting LISP compiler
in 440 lines of (dynamically scoped) LISP and a lexically scoped
interpreter (written using that compiler) in 150 lines.
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Paul Rubin
2020-10-12 20:30:25 UTC
Permalink
Post by Nils M Holm
The earliest SIOD I remember was almost twice as big as Kilo LISP.
Hmm that could be. It had different goals, I think.
Post by Nils M Holm
My upcoming book shows an implementation of a self-hosting LISP compiler
in 440 lines of (dynamically scoped) LISP and a lexically scoped
interpreter (written using that compiler) in 150 lines.
Nice, looking forward to it! But is that a reasonably complete Lisp
with read, eval, print, gc, macros, and basic user functions like
arithmetic? Any chance of a lexical scope compiler?
Nils M Holm
2020-10-13 09:50:20 UTC
Permalink
Post by Paul Rubin
Post by Nils M Holm
The earliest SIOD I remember was almost twice as big as Kilo LISP.
Hmm that could be. It had different goals, I think.
Definitely! Even the earliest SIOD was much more complete than Kilo LISP.
Post by Paul Rubin
Post by Nils M Holm
My upcoming book shows an implementation of a self-hosting LISP compiler
in 440 lines of (dynamically scoped) LISP and a lexically scoped
interpreter (written using that compiler) in 150 lines.
Nice, looking forward to it! But is that a reasonably complete Lisp
with read, eval, print, gc, macros, and basic user functions like
arithmetic?
In 800 lines you get the compiler plus READ, PRINT, INTERN, MAPCAR, etc,
all written in LISP, all completely self-hosting.
Post by Paul Rubin
Any chance of a lexical scope compiler?
Not this time! However:

Compiling Lambda Calculus shows different implementation models for
Scheme, including compilation to C: http://www.t3x.org/clc/index.html
Code is in the public domain and can be downloaded on the web page.

LISP System Implementation implements some optimizations that the
above discusses but does not implement: http://www.t3x.org/lsi/index.html
It compiles to bytecode, though, and code is in C. Sources are here:
https://www.t3x.org/lisp9/index.html
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Paul Rubin
2020-10-13 23:31:49 UTC
Permalink
Post by Nils M Holm
In 800 lines you get the compiler plus READ, PRINT, INTERN, MAPCAR, etc,
all written in LISP, all completely self-hosting.
Cool, by self-hosting do you mean the compiler generates C code? How
does CONS work?
Post by Nils M Holm
Compiling Lambda Calculus shows different implementation models for
Scheme, including compilation to C: http://www.t3x.org/clc/index.html
Code is in the public domain and can be downloaded on the web page.
Sounds nice!
Nils M Holm
2020-10-14 08:42:52 UTC
Permalink
Post by Paul Rubin
Post by Nils M Holm
In 800 lines you get the compiler plus READ, PRINT, INTERN, MAPCAR, etc,
all written in LISP, all completely self-hosting.
Cool, by self-hosting do you mean the compiler generates C code? How
does CONS work?
Yes, the compiler generates C code.

CONS removes a cell from the freelist and initializes it with the
arguments of CONS. :)

But that's not what you meant!

Yes, it does GC. No, the GC is not written in LISP, but it can, and
the book contains a GC implementation in LISP and instructions on how
to integrate it into the system. I am not going to do *all* the work
for you! ;)
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
none) (albert
2020-10-16 12:20:27 UTC
Permalink
Post by Nils M Holm
Post by Paul Rubin
Post by Nils M Holm
Even smaller: https://t3x.org/klisp/index.html
This looks cute though I'm not sure how its size compares with early
SIOD.
The earliest SIOD I remember was almost twice as big as Kilo LISP.
Post by Paul Rubin
Lexical scope is maybe best implemented in a compiler (at least a
rudimentary one, like to a stack VM) rather than by direct
interpretation.
I agree that it is best implemented *efficiently* in a compiler. It
is very easy to implement when using deep binding in an interpreter.
Post by Paul Rubin
I have a joke that I want to use that VM as a target interpreter for a
microprocessor oriented subset of Haskell. I'm going to call it
Control-H, and the file extension will be a backspace character ;).
:)
Post by Paul Rubin
I think it should be possible to write a usable small Lisp or Scheme
system with no more than a few hundred lines of C or asm, for a low
level interpreter. The rest would be written in Lisp (or Scheme)
itself. Certainly the reader and printer should be written that way.
My upcoming book shows an implementation of a self-hosting LISP compiler
in 440 lines of (dynamically scoped) LISP and a lexically scoped
interpreter (written using that compiler) in 150 lines.
I wonder if self hosting in the lisp world means the same as in the
c world.
When I was hired to revamp embedded software of molding machines I
had to use the c-compiler all day. The c-compiler had unsufficient
seats, to accommodate regular production and me, so we ordered
an extra license from Sun. The license protection was crappy, so we
did not in fact have an extra seat. We were fed up with that.
So we used the (SUN) c-compiler to compile the GNU-compiler.
Then we recompiled the GNU-compiler using the GNU-compiler.
Now we had a c-compiler that did all we needed, and no licensing
annoyances. No dependancy on any external tool remained we got the
c-compiler running. It was fully functional and quickly replaced
the Sun c-compilers for everything.

Is self hosting lisp anywhere near that in capability?
Of course the GNU-compiler had a part targeted to sun architecture,
but that is what it made practical.
Post by Nils M Holm
--
Groetjes Albert
--
This is the first day of the end of your life.
It may not kill you, but it does make your weaker.
If you can't beat them, too bad.
***@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Nils M Holm
2020-10-16 13:20:01 UTC
Permalink
Post by none) (albert
Is self hosting lisp anywhere near that in capability?
Of course the GNU-compiler had a part targeted to sun architecture,
but that is what it made practical.
Self-hosting in this case means that the compiler can compile its
own code. Since it compiles to C, it obviously needs a C compiler,
too.
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
Zyni Moë
2020-10-16 14:27:12 UTC
Permalink
Post by none) (albert
Is self hosting lisp anywhere near that in capability?
Of course the GNU-compiler had a part targeted to sun architecture,
but that is what it made practical.
Many (most?) lisps have been self-hosting in this way. If running on
platforms where OS interface is most conveniently accessed in C then often
they have a C shim of some kind, and some do GC etc in C. But most (?)
Lisp compilers are written in the language compile. For a long time
(perhaps still) CMUCL can't be built without a running CMUCL. SBCL can be
built with other CLs.
--
the small snake
Paul Rubin
2020-10-16 15:26:19 UTC
Permalink
Post by none) (albert
I wonder if self hosting in the lisp world means the same as in the
c world.
I guess I had been thinking of something more like a metacompiled Forth.
There are some Lisps where the entire system is written in Lisp,
including an assembler written in Lisp, similar to Forth assemblers, so
the Lisp compiler can produce executable machine code files for the OS
of choice. You need a running Lisp to bootstrap from (maybe on another
machine) but after that you don't need anything.

Most of the time, Lisp runs under an OS rather than on bare metal, but
there are bare metal Lisps and Lisp OS's as well, just like Forth.
There have also been Lisp cpu's with hardware support for type tags and
GC etc., along with Lisp OS's that ran on them. In that way, Lisp had
sort of a parallel evolution to Forth, but on a much grander scale.
luserdroog
2020-10-11 19:33:35 UTC
Permalink
Post by Paul Rubin
Post by luserdroog
I've heard good things about L.i.s.p. but never wanted to cough up
the money.... What about Burge, /Recursive Programming Techniques/?
I'm not familiar with either of those, but I think SICP should be enough
to get you going.
Burge seems like a really nice book. It's from '75 so older than
Anatomy ('78) but the syntax is easier to look at (fewer greek letters,
nicer font). It says it's built upon Landin's SECD machine.
Section 2.11 does seem to be talking about closures and converting
lambdas into closures.
Paul Rubin
2020-10-12 00:23:43 UTC
Permalink
Burge seems like a really nice book. ... nicer font). It says it's
built upon Landin's SECD machine. Section 2.11 does seem to be
talking about closures and converting lambdas into closures.
I might look for it sometime, but you might do better reading the Rabbit
papers (Lambda, the ultimate <whatever>) directly. I'd really start
with SICP though. If you want to go more hardcore than that, you might
look at "The Implementation of Functional Programming Languages" by
Simon Peyton Jones:

https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/

It is mostly about lazy evaluation (a la Haskell) via graph reduction,
but it can get you into the mindset.

I also liked Harper's "Practical Foundations of Programming Languages"
though it is more theoretical (has greek letters) and a lot of it is
about type systems:

http://www.cs.cmu.edu/~rwh/pfpl/index.html

He is one of the inventors of ML and dislikes Haskell, so be aware of
that bias. Before the book was published there was an online draft of
the first edition that I think is still in the Wayback Machine, and
there's now an "abbreviated" (560 page) version of the 2nd edition
there.
luserdroog
2020-10-12 08:03:48 UTC
Permalink
Post by luserdroog
Post by Paul Rubin
Post by luserdroog
I've heard good things about L.i.s.p. but never wanted to cough up
the money.... What about Burge, /Recursive Programming Techniques/?
I'm not familiar with either of those, but I think SICP should be enough
to get you going.
Burge seems like a really nice book. It's from '75 so older than
Anatomy ('78) but the syntax is easier to look at (fewer greek letters,
nicer font). It says it's built upon Landin's SECD machine.
Section 2.11 does seem to be talking about closures and converting
lambdas into closures.
Interesting, more than that it's also doing decomposition of
arguments. For an environment it seems to build a list of
pairs of lvalue pointing to place in argument and lvalue
pointing to patch point in the function body. In the figure
the pairs are written with the parameter name next to them
but it appears that the parameter name doesn't really need
to exist anymore in the data structure.
luserdroog
2020-10-14 23:57:42 UTC
Permalink
Post by Paul Rubin
Post by luserdroog
I've heard good things about L.i.s.p. but never wanted to cough up
the money.... What about Burge, /Recursive Programming Techniques/?
I'm not familiar with either of those, but I think SICP should be enough
to get you going. The Little Schemer has its own following so you might
check it out, but I myself have never understood it. If you can read C,
you might examine the source code of a simple Scheme implementation
SIOD is still quite small and has some implementation notes, but the
http://people.delphiforums.com/gjc//siod.html
It is around if you look for it, or I can probably dig it up for you if
you want it.
Thanks a bunch. That led me to "The Art of the Interpreter"

https://dspace.mit.edu/bitstream/handle/1721.1/6094/AIM-453.pdf
Nils M Holm
2020-10-11 07:27:47 UTC
Permalink
Post by luserdroog
Thanks. I pulled it off of the shelf. Also Anatomy of Lisp.
I've heard good things about L.i.s.p. but never wanted to cough up
the money.
Anatomy of LISP, being written in the 1970's, does not discuss
lexical binding, IIRC. It is still an excellent book, though!
--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org
luserdroog
2020-10-11 01:14:15 UTC
Permalink
Post by Kaz Kylheku
Post by luserdroog
them will need modification to pass the env and return a modified one.
So I suppose getting rid of the global env is the first step.
Yes, and no.
Let me now describe a different implementation strategy.
Dynamnic scope can be made to behave like lexical scope, yet
retain the dynamism.
Firstly, let me say that even if you pass the environment around
everywhere and avoid the global variable, you can still have dynamic
scope. You can do that by making closures dumb (no environment stored in
them) and by passing the envrionment even into the function application
machinery, so that function bodies are evaluated in a scope which
includes the passed-down environment extended with the parameter
bindings (and not any closed environment).
About 17 years ago I wrote a dialect called VoqLisp (in C++) which
passed the environment around, but passed it into the function calling
(let ((*foo* 42))
(fun)) ;; fun could see *foo*
Yet, lexical closures worked in this dialect.
How that worked was: each environment frame carried a "is-top-level"
flag. Whenever a function was called, the brand new environment
frame which was created for it, and pushed onto the environment
stack, had this flag set to true.
The lambda operator created a closure by taking a delimited slice of the
environment, up to and including the closest frame marked is-top-level.
It made a copy of this environment and stuck it into the closure.
The invocation of a lambda spliced the captured environment
onto the environment. So that is to say, a function would see its
parameter bindings first, the captured environment slice second,
and after that, the current dynamic scope.
(In retrospect, all of this is eerily similar to one of the possible
strategies of implementing delimited closures. My implementation was
doing with variable bindings what delimited closures do with the entire
control context.)
This does make it sound like I need Weizenbaum enviroments or something
like it. The environment needs more structure than just a cons list
of assoc pairs. So that will require wrapping/redesigning ASSOC as well
as SET(Q) and the DEFUN behavior*.

Then the LAMBDA behavior needs to create a closure. At first I feared that
it needs to inspect the body to identify any free variables then set up
some kind of copy-on-value-return link for each one.

But, instead the closure just collects a few pointers to whole env "slices"
(where a slice is maybe a simple association list). So the overall
env structure could be a list of association lists. And we push and pop
the "stack" by linking new association lists onto the front of it.

So is it ok to still have SET/SETQ modifying the "global" frame?
I don't have LET or PROGN or anything too fancy implemented yet.



*behavior here is the action performed by EVAL upon the special form.
Zyni Moë
2020-10-11 09:58:26 UTC
Permalink
Post by luserdroog
So is it ok to still have SET/SETQ modifying the "global" frame?
I don't have LET or PROGN or anything too fancy implemented yet.
setq should mutate the innermost binding of a variable, not global binding,
unless that is innermost.
--
the small snake
luserdroog
2020-10-11 18:44:38 UTC
Permalink
Post by Zyni Moë
Post by luserdroog
So is it ok to still have SET/SETQ modifying the "global" frame?
I don't have LET or PROGN or anything too fancy implemented yet.
setq should mutate the innermost binding of a variable, not global binding,
unless that is innermost.
Thanks. That makes a lot more sense.
Loading...