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

Groups > comp.lang.lisp > #28579 > unrolled thread

The simplest compiler possible

Back to article view | Back to comp.lang.lisp

Contents

  The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-29 19:54 +0100
    Re: The simplest compiler possible Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-29 19:18 +0000
      Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-30 02:22 +0100
        Re: The simplest compiler possible Paul Rubin <no.email@nospam.invalid> - 2017-01-29 18:13 -0800
          Re: The simplest compiler possible Barry Margolin <barmar@alum.mit.edu> - 2017-01-30 12:12 -0500
            Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-30 18:50 +0100
              Re: The simplest compiler possible rpw3@rpw3.org (Rob Warnock) - 2017-01-31 07:11 +0000
                Re: The simplest compiler possible Paul Rubin <no.email@nospam.invalid> - 2017-01-30 23:17 -0800
                  Re: The simplest compiler possible Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-31 14:32 +0000
                    Re: The simplest compiler possible Barry Margolin <barmar@alum.mit.edu> - 2017-01-31 15:12 -0500
                Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-31 11:39 +0100
                  Re: The simplest compiler possible Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-31 14:19 +0000
            Re: The simplest compiler possible Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-30 19:10 +0000
              Re: The simplest compiler possible Barry Margolin <barmar@alum.mit.edu> - 2017-01-30 16:19 -0500
                Re: The simplest compiler possible Paul Rubin <no.email@nospam.invalid> - 2017-01-30 15:00 -0800
                  Re: The simplest compiler possible Christian Jullien <christian.jullien@novasparks.com> - 2017-01-30 23:19 -0800
                  Re: The simplest compiler possible Barry Margolin <barmar@alum.mit.edu> - 2017-01-31 15:03 -0500
    Re: The simplest compiler possible anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-01-31 13:17 +0000
      Re: The simplest compiler possible Barry Margolin <barmar@alum.mit.edu> - 2017-01-31 15:10 -0500
        Re: The simplest compiler possible Elias Mårtenson <lokedhs@gmail.com> - 2017-01-31 20:08 -0800
          Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-02-01 12:12 +0100
    Re: The simplest compiler possible a.daniel.eliason@gmail.com - 2017-02-22 12:44 -0800
      Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-02-23 12:14 +0100

Page 1 of 2  [1] 2  Next page →

#28579 — The simplest compiler possible

The following experimental compiler has an interesting comment
on the claim that lisp can be defined in lisp.
https://github.com/kragen/stoneknifeforth
A number of practical issues are swept under the rug, as I have
discovered in my recent attempts too. As an example I can give the
complications in the reader that has to decide which tokens are
evaluated and which are not. (I apologize if this is not a careful
enough formulation such that some may take offense. The README of
that project explains it better.)

The compiler can really can recompile itself. No hand waving, real
executables, which require some assembly.

In a search for the simplest compiler that can do so,
the author arrived at Forth as a starting point rather than lisp.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [next] | [standalone]

#28580

On 2017-01-29, Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
> The following experimental compiler has an interesting comment
> on the claim that lisp can be defined in lisp.
> https://github.com/kragen/stoneknifeforth

I doubt it.

Most Common Lisp implementations have compilers.

I'm not aware of any whose compiler is *not* written in Lisp. (Anyone?)

So proof of concept is hardly required.

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

#28582

In article <20170129110544.859@kylheku.com>,
Kaz Kylheku  <221-501-9011@kylheku.com> wrote:
>On 2017-01-29, Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
>> The following experimental compiler has an interesting comment
>> on the claim that lisp can be defined in lisp.
>> https://github.com/kragen/stoneknifeforth
>
>I doubt it.

You doubt that there is interesting comment?
>
>Most Common Lisp implementations have compilers.
>
>I'm not aware of any whose compiler is *not* written in Lisp. (Anyone?)
>
>So proof of concept is hardly required.

I do not doubt that lisp can be defined in lisp.

By the way, does
   make clisp
work on a system without gcc installed?

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#28584

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> By the way, does
>    make clisp
> work on a system without gcc installed?

Clisp is written partly in C, so building it requires a C compiler.

There are plenty of Lisps written in Lisp that don't contain any C at
all.  Of course you need a Lisp system to build them instead.

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

#28595

In article <87sho1z44e.fsf@nightsong.com>,
 Paul Rubin <no.email@nospam.invalid> wrote:

> albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> > By the way, does
> >    make clisp
> > work on a system without gcc installed?
> 
> Clisp is written partly in C, so building it requires a C compiler.
> 
> There are plenty of Lisps written in Lisp that don't contain any C at
> all.  Of course you need a Lisp system to build them instead.

And C compilers are mostly written in C. There's nothing very special 
about this. Anyone who wonders where the first one came from needs to 
google "bootstrapping".

In the case of Lisp, it's hard to implement it in any other language, 
because you need a Lisp implementation to expand macros and reader 
macros. So if the compiler isn't written in Lisp, it has to emulate a 
Lisp implementation internally, which would probably be an order of 
magnitude harder.

Few other languages have such an incestuous relationship between 
compilation and execution, so you can implement them in whatever 
language you find most convenient.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

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

#28597

In article <barmar-60105B.12125730012017@88-209-239-213.giganet.hu>,
Barry Margolin  <barmar@alum.mit.edu> wrote:
<SNIP>
>In the case of Lisp, it's hard to implement it in any other language,
>because you need a Lisp implementation to expand macros and reader
>macros. So if the compiler isn't written in Lisp, it has to emulate a
>Lisp implementation internally, which would probably be an order of
>magnitude harder.

This is about the kernel of what stoneknifeforth is about.

It is harder to maintain that defining lisp in lisp is educational or
insightful, the more complicated and powerful the lisp you start with
must be.
Of course MacCarthy's original article gives insight.
If you look however how lambda and environments are described,
then try to implement them, you realize that they are leaning
towards being pseudocode rather than executable lisp.
E.g. lambda ask for a textual replacement system that is non-trivial.

If it is written using only lisp it has to deal with machinecode in
one form or another. Those who never have written a compiler from
scratch find it hard to realize that.

> Few other languages have such an incestuous relationship between
>compilation and execution, so you can implement them in whatever
>language you find most convenient.

Forth of course is also incestuous, among a lot of other bad
properties.

>
>--
>Barry Margolin, barmar@alum.mit.edu

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#28602

Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
+---------------
| Of course MacCarthy's original article gives insight.
| If you look however how lambda and environments are described,
| then try to implement them, you realize that they are leaning
| towards being pseudocode rather than executable lisp.
| E.g. lambda ask for a textual replacement system that is non-trivial.
+---------------

I don't know where you heard that idea, but it's incorrect.
In the programming language Lisp, the lambda operator does *NOT*
require a "textual replacement" of any kind [nor does evaluation
in general]. Once a form has been read -- *long* before it is
evaluated! -- there is no "text" left at all, just Lisp objects.
[Obviously, here I'm ignoring Lisp objects which happen to be
strings, but those are not necessary for evaluation to work.]

+---------------
| If it is written using only lisp it has to deal with machinecode
| in one form or another. Those who never have written a compiler
| from scratch find it hard to realize that.
+---------------

Look up the term "LAP" [Lisp Assembly Program] and you'll discover
that dealing with machine code as Lisp data is almost as old as
Lisp itself. [Hint: See Appendix C of the MIT Lisp 1.5 manual,
circa 1962.]


-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

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

#28603

rpw3@rpw3.org (Rob Warnock) writes:
> | E.g. lambda ask for a textual replacement system that is non-trivial.
> I don't know where you heard that idea, but it's incorrect.
> In the programming language Lisp, the lambda operator does *NOT*
> require a "textual replacement" of any kind

Church's lambda calculus called for textual substitution aka beta
reduction.  Lisp implements it in a different way.

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

#28610

On 2017-01-31, Paul Rubin <no.email@nospam.invalid> wrote:
> rpw3@rpw3.org (Rob Warnock) writes:
>> | E.g. lambda ask for a textual replacement system that is non-trivial.
>> I don't know where you heard that idea, but it's incorrect.
>> In the programming language Lisp, the lambda operator does *NOT*
>> require a "textual replacement" of any kind
>
> Church's lambda calculus called for textual substitution aka beta
> reduction.  Lisp implements it in a different way.

Lambda calculus is an extension to mathematics which anonymizes
functions, allowing them to to be literal terms like numbers or sets,
and appear as values of variables, including function arguments.
That's the "big deal" in lambda calculus.

Lambda calculus isn't Lisp. It doesn't have code made up of conses
and atoms. It doesn't have EVAL or QUOTE. It doesn't have symbols
as a data type. (Term substitutions in lambda calculus manipulation are
sort of quoting, but they are outside of lambda calculus. Just like
simplifying a polynomial is outside of algebra.)

Also, Lisp was originally dynamically scoped, whereas lambda calculus
has lexical scope.

Lambda calculus can also come in a typed variety, whereas Lisp
is dynamic.

Even though "lambda calculus" has "lambda" in it, and lisp has lambda,
there is a stronger connection between lambda calculus and the pure
fucntional languages than between lambda calculus and Lisp.

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

#28616

In article <20170131062108.962@kylheku.com>,
 Kaz Kylheku <221-501-9011@kylheku.com> wrote:

> On 2017-01-31, Paul Rubin <no.email@nospam.invalid> wrote:
> > rpw3@rpw3.org (Rob Warnock) writes:
> >> | E.g. lambda ask for a textual replacement system that is non-trivial.
> >> I don't know where you heard that idea, but it's incorrect.
> >> In the programming language Lisp, the lambda operator does *NOT*
> >> require a "textual replacement" of any kind
> >
> > Church's lambda calculus called for textual substitution aka beta
> > reduction.  Lisp implements it in a different way.
> 
> Lambda calculus is an extension to mathematics which anonymizes
> functions, allowing them to to be literal terms like numbers or sets,
> and appear as values of variables, including function arguments.
> That's the "big deal" in lambda calculus.
> 
> Lambda calculus isn't Lisp. It doesn't have code made up of conses
> and atoms. It doesn't have EVAL or QUOTE. It doesn't have symbols
> as a data type. (Term substitutions in lambda calculus manipulation are
> sort of quoting, but they are outside of lambda calculus. Just like
> simplifying a polynomial is outside of algebra.)
> 
> Also, Lisp was originally dynamically scoped, whereas lambda calculus
> has lexical scope.
> 
> Lambda calculus can also come in a typed variety, whereas Lisp
> is dynamic.
> 
> Even though "lambda calculus" has "lambda" in it, and lisp has lambda,
> there is a stronger connection between lambda calculus and the pure
> fucntional languages than between lambda calculus and Lisp.

I think it's most accurate to say that the design of Lisp was inspired 
by lambda calculus, or took some ideas from it, but not intended to be 
an actual implementation of it.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

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

#28607

In article <o6pdaj$465$1@dont-email.me>, Rob Warnock <rpw3@rpw3.org> wrote:
>Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
>+---------------
>| Of course MacCarthy's original article gives insight.
>| If you look however how lambda and environments are described,
>| then try to implement them, you realize that they are leaning
>| towards being pseudocode rather than executable lisp.
>| E.g. lambda ask for a textual replacement system that is non-trivial.
>+---------------
>
>I don't know where you heard that idea, but it's incorrect.
>In the programming language Lisp, the lambda operator does *NOT*
>require a "textual replacement" of any kind [nor does evaluation
>in general]. Once a form has been read -- *long* before it is
>evaluated! -- there is no "text" left at all, just Lisp objects.
>[Obviously, here I'm ignoring Lisp objects which happen to be
>strings, but those are not necessary for evaluation to work.]

I was talking about a literal implementation based on
that seminal paper only.

>
>+---------------
>| If it is written using only lisp it has to deal with machinecode
>| in one form or another. Those who never have written a compiler
>| from scratch find it hard to realize that.
>+---------------
>
>Look up the term "LAP" [Lisp Assembly Program] and you'll discover
>that dealing with machine code as Lisp data is almost as old as
>Lisp itself. [Hint: See Appendix C of the MIT Lisp 1.5 manual,
>circa 1962.]

Of course it is. Thanks for the search term though.

>
>
>-Rob

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#28609

On 2017-01-31, Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
> In article <o6pdaj$465$1@dont-email.me>, Rob Warnock <rpw3@rpw3.org> wrote:
>>Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> wrote:
>>+---------------
>>| Of course MacCarthy's original article gives insight.
>>| If you look however how lambda and environments are described,
>>| then try to implement them, you realize that they are leaning
>>| towards being pseudocode rather than executable lisp.
>>| E.g. lambda ask for a textual replacement system that is non-trivial.
>>+---------------
>>
>>I don't know where you heard that idea, but it's incorrect.
>>In the programming language Lisp, the lambda operator does *NOT*
>>require a "textual replacement" of any kind [nor does evaluation
>>in general]. Once a form has been read -- *long* before it is
>>evaluated! -- there is no "text" left at all, just Lisp objects.
>>[Obviously, here I'm ignoring Lisp objects which happen to be
>>strings, but those are not necessary for evaluation to work.]
>
> I was talking about a literal implementation based on
> that seminal paper only.

Luckily, that sort of mistake was avoided sixty years ago.

Can we move on?

(By "we", I presently mean "you".)

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

#28598

On 2017-01-30, Barry Margolin <barmar@alum.mit.edu> wrote:
> In article <87sho1z44e.fsf@nightsong.com>,
>  Paul Rubin <no.email@nospam.invalid> wrote:
>
>> albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>> > By the way, does
>> >    make clisp
>> > work on a system without gcc installed?
>> 
>> Clisp is written partly in C, so building it requires a C compiler.
>> 
>> There are plenty of Lisps written in Lisp that don't contain any C at
>> all.  Of course you need a Lisp system to build them instead.
>
> And C compilers are mostly written in C. There's nothing very special 
> about this. Anyone who wonders where the first one came from needs to 
> google "bootstrapping".
>
> In the case of Lisp, it's hard to implement it in any other language, 
> because you need a Lisp implementation to expand macros and reader 
> macros.

Having implemented macro expansion in C (including lexical macros,
symbol macros and all, with proper scoping), I have to disagree here.

However, C is a terrible language for doing more complex things, like
compilers: even if you have the Lisp primitives at your disposal, and
garbage collection and all.

The main reason you might do macro expansion in C is because you don't
have a Lisp compiler (yet). The macro expander isn't a compiler; if you
write it Lisp, it won't compile itself to be any faster.  By contrast, a
compiler will compile itself. So the major reason for even contemplating
writing it in C disappears.

Also, here is a thought, the compiler compiling itself provides
a powerful test case for the compiler! Okay, here you are, about to
write a Lisp compiler. It's going to need rigorous testing. So what do you
do? Start cranking out thousands of lines of C code which doesn't
contribute anything to the testing? Stupid, right?

> So if the compiler isn't written in Lisp, it has to emulate a 
> Lisp implementation internally, which would probably be an order of 
> magnitude harder.

Right, but Lisp implementations bootstrapped from C have that Lisp
implementation internally. You can write "C" like

   if (consp(x)) {
     val sym = car(x);
     ...
   }

that will certainly take you as far as expanding out macros.

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

#28600

In article <20170130105555.836@kylheku.com>,
 Kaz Kylheku <221-501-9011@kylheku.com> wrote:

> On 2017-01-30, Barry Margolin <barmar@alum.mit.edu> wrote:
> > In article <87sho1z44e.fsf@nightsong.com>,
> >  Paul Rubin <no.email@nospam.invalid> wrote:
> >
> >> albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> >> > By the way, does
> >> >    make clisp
> >> > work on a system without gcc installed?
> >> 
> >> Clisp is written partly in C, so building it requires a C compiler.
> >> 
> >> There are plenty of Lisps written in Lisp that don't contain any C at
> >> all.  Of course you need a Lisp system to build them instead.
> >
> > And C compilers are mostly written in C. There's nothing very special 
> > about this. Anyone who wonders where the first one came from needs to 
> > google "bootstrapping".
> >
> > In the case of Lisp, it's hard to implement it in any other language, 
> > because you need a Lisp implementation to expand macros and reader 
> > macros.
> 
> Having implemented macro expansion in C (including lexical macros,
> symbol macros and all, with proper scoping), I have to disagree here.

How easy was it, compared to doing it in Lisp?

> 
> However, C is a terrible language for doing more complex things, like
> compilers: even if you have the Lisp primitives at your disposal, and
> garbage collection and all.
> 
> The main reason you might do macro expansion in C is because you don't
> have a Lisp compiler (yet). The macro expander isn't a compiler; if you
> write it Lisp, it won't compile itself to be any faster.  By contrast, a
> compiler will compile itself. So the major reason for even contemplating
> writing it in C disappears.
> 
> Also, here is a thought, the compiler compiling itself provides
> a powerful test case for the compiler! Okay, here you are, about to
> write a Lisp compiler. It's going to need rigorous testing. So what do you
> do? Start cranking out thousands of lines of C code which doesn't
> contribute anything to the testing? Stupid, right?
> 
> > So if the compiler isn't written in Lisp, it has to emulate a 
> > Lisp implementation internally, which would probably be an order of 
> > magnitude harder.
> 
> Right, but Lisp implementations bootstrapped from C have that Lisp
> implementation internally. You can write "C" like
> 
>    if (consp(x)) {
>      val sym = car(x);
>      ...
>    }
> 
> that will certainly take you as far as expanding out macros.

Typically, the way many languages get bootstrapped is by using a subset 
of the language in the initial implementation. So you might write a 
simple compiler that doesn't use macros, so the compiler written in C 
doesn't need to have a macro expander.

In the case of Lisp, another way to bootstrap it is by using a Lisp 
interpreter to run the initial compiler. So you get the full power of 
the language without needing a compiler at all.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

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

#28601

Barry Margolin <barmar@alum.mit.edu> writes:
>> Having implemented macro expansion in C (including lexical macros,
>> symbol macros and all, with proper scoping), I have to disagree here.
> How easy was it, compared to doing it in Lisp?

I've implemented Lisp in C, though mine was dynamically scoped, back
when I thought that was cool.

The C code ends up looking about like Lisp code once enough of the low
level functions are in place.  Macroexpand looks something like:

  // macro is something like (macro lambda (x) .... )  
  Object macroexpand(Object macro, Object form) {
    return funcall(cdr(macro), form);
  }

and so on.  The object allocator is connected up to the garbage
collector as you'd want, so evaluation does the right thing.  The only
extra work is that if you create an intermediate value and then call
eval, you have to save the intermediate value on the control stack, so
the GC will mark it if it runs during the eval.

Emacs Lisp is also written more or less that way, as a well-known
example.

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

#28604

Here https://en.wikipedia.org/wiki/OpenLisp#Compiler
You can see how a Lisp program can be translated to intermediate LAP then transformed in C to be finally compiled as native machine code by a pure C compiler. Many other technics exist.


On Tuesday, January 31, 2017 at 12:00:52 AM UTC+1, Paul Rubin wrote:
> Barry Margolin <barmar@alum.mit.edu> writes:
> >> Having implemented macro expansion in C (including lexical macros,
> >> symbol macros and all, with proper scoping), I have to disagree here.
> > How easy was it, compared to doing it in Lisp?
> 
> I've implemented Lisp in C, though mine was dynamically scoped, back
> when I thought that was cool.
> 
> The C code ends up looking about like Lisp code once enough of the low
> level functions are in place.  Macroexpand looks something like:
> 
>   // macro is something like (macro lambda (x) .... )  
>   Object macroexpand(Object macro, Object form) {
>     return funcall(cdr(macro), form);
>   }
> 
> and so on.  The object allocator is connected up to the garbage
> collector as you'd want, so evaluation does the right thing.  The only
> extra work is that if you create an intermediate value and then call
> eval, you have to save the intermediate value on the control stack, so
> the GC will mark it if it runs during the eval.
> 
> Emacs Lisp is also written more or less that way, as a well-known
> example.

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

#28614

In article <878tpsywym.fsf@nightsong.com>,
 Paul Rubin <no.email@nospam.invalid> wrote:

> Barry Margolin <barmar@alum.mit.edu> writes:
> >> Having implemented macro expansion in C (including lexical macros,
> >> symbol macros and all, with proper scoping), I have to disagree here.
> > How easy was it, compared to doing it in Lisp?
> 
> I've implemented Lisp in C, though mine was dynamically scoped, back
> when I thought that was cool.

Compiler or interpreter?

> 
> The C code ends up looking about like Lisp code once enough of the low
> level functions are in place.  Macroexpand looks something like:
> 
>   // macro is something like (macro lambda (x) .... )  
>   Object macroexpand(Object macro, Object form) {
>     return funcall(cdr(macro), form);
>   }

If you have a funcall() function, it seems like you have to have all the 
code of the interpreter in your compiler.

> 
> and so on.  The object allocator is connected up to the garbage
> collector as you'd want, so evaluation does the right thing.  The only
> extra work is that if you create an intermediate value and then call
> eval, you have to save the intermediate value on the control stack, so
> the GC will mark it if it runs during the eval.
> 
> Emacs Lisp is also written more or less that way, as a well-known
> example.

AFAIK, the Emacs Lisp compiler is written in Lisp, it compiles to byte 
code. Only the interpreter and some supporting low-level code like 
redisplay is in C.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

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

#28608

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>The following experimental compiler has an interesting comment
>on the claim that lisp can be defined in lisp.

The issue is not that it cannot, but that the typical meta-circular
interpreter, especially the minimal ones, just inherits so many traits
from its substrate that it does not serve as a specification of the
language, at best of a tiny aspect of the language.  It's almost as if
you said: Look, here's a meta-circular interpreter for a Forth string:

: forth-interpreter ( ... c-addr u -- ... ) evaluate ;

And even the classical user-defined text interpreter just explains
text interpretation, but inherits all the words from the substrate.

The author tries to avoid this issue by using IA-32 machine language
as the substrate, and he tries to use as little literal machine
language as possible.

If you use machine language as a substrate, it's no surprise that the
minimal language is more in the direction of Forth than Lisp or other
math-inspired languages.  You still get some inheritance: E.g., his
compiler inherits the character encoding of the system it works on.
How would a different architecture (maybe one of the ancient ones with
died-out charactersitics like decimal number representation, or
ones-complement arithmetics) affect the result?

With more mathematical substrates, such as a universal Turing machine,
or the combinators S and K, what would the resulting minimal language
look like.

>https://github.com/kragen/stoneknifeforth

Most notable here are

https://github.com/kragen/stoneknifeforth/blob/master/README.md
https://github.com/kragen/stoneknifeforth/blob/master/tinyboot1.tbf1

The first explains the motivations and some design decisions, the
second seems to the the actual source code of the compiler.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#28615

In article <2017Jan31.141722@mips.complang.tuwien.ac.at>,
 anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

> albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> >The following experimental compiler has an interesting comment
> >on the claim that lisp can be defined in lisp.
> 
> The issue is not that it cannot, but that the typical meta-circular
> interpreter, especially the minimal ones, just inherits so many traits
> from its substrate that it does not serve as a specification of the
> language, at best of a tiny aspect of the language.  It's almost as if
> you said: Look, here's a meta-circular interpreter for a Forth string:
> 
> : forth-interpreter ( ... c-addr u -- ... ) evaluate ;
> 
> And even the classical user-defined text interpreter just explains
> text interpretation, but inherits all the words from the substrate.

These discussions always remind me of the surprising reaction I had when 
I looked at some of the Lisp Machine source code:

(defun cons (car cdr)
  (cons car cdr))
(defun car (cons)
  (car cons))
(defun cdr (cons)
  (cdr cons))

No, it's not infinite recursion, it depends on the fact that the 
compiler open-codes these functions. The purpose of this is to get the 
code and debugging info attached to the function name symbols, so that 
FUNCALL and the interpreter can execute calls to these functions.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

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

#28618

On Wednesday, 1 February 2017 04:10:54 UTC+8, Barry Margolin  wrote:

> These discussions always remind me of the surprising reaction I had when 
> I looked at some of the Lisp Machine source code:
> 
> (defun cons (car cdr)
>   (cons car cdr))
> (defun car (cons)
>   (car cons))
> (defun cdr (cons)
>   (cdr cons))
> 
> No, it's not infinite recursion, it depends on the fact that the 
> compiler open-codes these functions. The purpose of this is to get the 
> code and debugging info attached to the function name symbols, so that 
> FUNCALL and the interpreter can execute calls to these functions.

I have exactly the same surprise when I started looking at the SBCL source code, which contains exactly the same thing. Very confusing until one learns about DEFINE-SOURCE-TRANSFORM.

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.lisp

csiph-web