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

Groups > comp.lang.forth > #54527 > unrolled thread

The simplest compiler possible

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

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 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 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 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 Gerard Sontag <gerardsontag@gmail.com> - 2017-02-03 01:08 -0800
      Re: The simplest compiler possible albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-02-03 10:23 +0100
        Re: The simplest compiler possible Gerard Sontag <gerardsontag@gmail.com> - 2017-02-03 02:34 -0800
      Re: The simplest compiler possible stephen@mpeforth.com (Stephen Pelc) - 2017-02-03 13:06 +0000

#54527 — 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]

#54528

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]

#54547

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]

#54565

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]

#54566

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]

#54575

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]

#54572

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]

#54574

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]

#54573

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]

#54579

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]

#54605

Le dimanche 29 janvier 2017 19:55:24 UTC+1, Albert van der Horst a écrit :
> ...
> The compiler can really can recompile itself. No hand waving, real
> executables, which require some assembly.
> 
> 
> 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
Albert,
Have a look at this page:
http://www.bayfronttechnologies.com/mc_workshop.html
You will fall in love.

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

#54606

In article <d8e6116a-cefe-4f26-a184-ec8acd81983f@googlegroups.com>,
Gerard Sontag  <gerardsontag@gmail.com> wrote:
>Le dimanche 29 janvier 2017 19:55:24 UTC+1, Albert van der Horst a =C3=A9cr=
>it=C2=A0:
>> ...
>> The compiler can really can recompile itself. No hand waving, real
>> executables, which require some assembly.
>>=20
>>=20
>> Groetjes Albert
>> --=20
>> Albert van der Horst, UTRECHT,THE NETHERLANDS
>> Economic growth -- being exponential -- ultimately falters.
>> albert@spe&ar&c.xs4all.nl &=3Dn http://home.hccnet.nl/a.w.m.van.der.horst
>Albert,
>Have a look at this page:
>http://www.bayfronttechnologies.com/mc_workshop.html
>You will fall in love.

For me it looks like the output of a buzz word generator.

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]

#54608

Le vendredi 3 février 2017 10:23:51 UTC+1, Albert van der Horst a écrit :
> In article <d8e6116a-cefe-4f26-a184-ec8acd81983f@googlegroups.com>,
> ...
> 
> For me it looks like the output of a buzz word generator.
> 
> 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
It can be at first, but if you take time to read (and maybe re-read) carrefully the tutorial you will see it's not.

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

#54609

On Fri, 3 Feb 2017 01:08:47 -0800 (PST), Gerard Sontag
<gerardsontag@gmail.com> wrote:

>Have a look at this page:
>http://www.bayfronttechnologies.com/mc_workshop.html
>You will fall in love.

I started/wrote my first proper compiler using META II on a
Marinchip M9900 systems. Aahh!

Stephen


-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [standalone]

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

csiph-web