A C++ implementation of Shen?

[Antti Ylikoski]

I'm planning to do, from TBoS:

Starred exercise 4) from TBoS, Page 181.  Find a language of your

choice and implement a compiler or interpreter for K-Lambda.

I'm thinking of the C++ language.

To my knowledge, there is not yet there an implementation of Shen for

C++, and I would interested in learning, whether this exercise,

K-Lambda in C++, could be extended to become a Shen implementation in

C++, with not a disproportionate amount of work.

Dr Tarver answered to this, that probably many people have done some

work with C++ and Shen, and I could utilize that work, in my project

of creating a Shen implementation for C++.

Therefore, I would be grateful if some wizards in here could inform me

of any existing work concerning C++ and Shen.

yours, Dr AJY

HELSINKI

The EU

[Mark Thom]

I'm currently working on a Shen implementation in C++, but the target language is LLVM IR.
It can be thought of as a kind of cross platform, JIT-compilable assembly language, which
can produce very fast code in capable hands (ie. probably not mine, for now).

Currently I'm following the techniques from chapter 10 of Lisp in Small Pieces, which discusses
the compilation of Scheme to C. LLVM IR has a number of nice features that C doesn't,
most importantly tail call optimization, built in support for exceptions and garbage collection
strategies, library level support for code generation, etc.

For GC, I plan on using Ravenbrook's Memory Pool System. I'm not decided on how the type
checker should be implemented just yet. Microsoft's Z3 theorem prover looks to be a promising
choice. I don't want to lean too heavily on third party libraries, but I'd be reproducing a lot of pre-existing,
high-quality work otherwise.

[Antti Ylikoski]

Thank you.

https://en.wikipedia.org/wiki/LLVM

Dr AJY

HELSINKI

The EU

[Willi Riha]

Anybody trying to implement Shen in C++ is either very naive or extremely talented!

For years, Mark has been suggesting that I have a go - after all, I knew C++ very well.

But I am neither naive, nor a genius, and therefore, I have not taken up Mark's suggestion.

I am not saying it cannot be done, and I hope somebody will be successful! 

The main stumbling block for me was, how to represent inhomogeneous list.

One probably has to implement one's own memory management.

or use some existing software - I am too old to get enthusiastic about this prospect.

Good luck!

W

Has anybody considered a Fortran implementation of Shen? Now there is a real challenge!

Don't say Fortran and COBOL are dead - my stepson's software firm is still maintaining bespoke

software written in these languages over 40 years ago!

[Mark Thom]

Here's the Variant class that I'm using, which is effectively a closed sum type:

https://thenewcpp.wordpress.com/2011/11/23/variadic-templates-part-1-2/

I'm using it to implement ASTs similar to what Quinnec uses in LiSP. I've found that
they're *much* more amenable to template metaprogramming than polymorphic classes.

[Willi Riha]

.... and the men in the white coats will be coming soon!

On Thursday, November 26, 2015 at 5:33:49 PM UTC, Antti Ylikoski wrote:

[Mark Thom]

Heh! Yes, C++ was on that track long before C++ 1x.

[Antti Ylikoski]

The first job that I ever got was, as a programmer creating some CAD

research software.

My boss, Dr Martti Mantyla (who is one of the most intelligent people

that I ever have met in my life) made an inhomogenous list with the

ATT Unix v6 C language.

The trick was absolutely simple.  The type "char *" was a

general-purpose pointer type in the ATT Unix v6 C.  So all addresses

were coerced (cast) into the type "char *".  That is all that there

was to it.

I even have seen an inhomogenous list being done in Pascal (there

exist several implementations of LISP in Pascal in order to be

portable).

Moreover: Isn't it the case that it is, mostly, only necessary to

implement the K-Lambda in C++, not the entire Shen?  The Shen system

that one loads from the Shen language site, is generated (SYSGENed)

from a set of files in K-Lambda?

Furthermore: I was planning to use the C++ language's own memory

management, not a full scale external memory management scheme?

I finally remark that I know the C++ language, but I'm not a highly

skilled programmer in C++!

yours, Dr AJY

HELSINKI

The EU

PS.  There exists a FORTRAN implementation of INTERLISP.

[Mark Thom]

You could just stick to implementing KLambda and bootstrapping from the sources,
yes. I plan to do that along the way, just to affirm that the code I'm producing is in a
reasonable place. Eventually, I would like to implement the other parts of the language in C++/LLVM,
just for the sake of performance. It would be nice to have a very fast, production quality
Prolog, type checker, pattern matcher, Shen-YACC, etc. all at the disposal of the REPL.

Implementing each of those things seems relatively straightforward. I'm mostly puzzling over
macro expansion and eval. My impression is that they're commonly written in whatever Lisp
they're intended to run under. Understandably so, as they're probably hell to program in an imperative
language.

As to using C++'s own memory management is concerned, I think you will wind
up with a garbage collector of some sort, perhaps pretty ramshackle but a GC just the same.
If you have a REPL, and objects that can persist between uses of the REPL,
that implies you need some way of discerning which objects are live and which can be junked.

[Antti Ylikoski]

It certainly will help you to see:

P H Winston, B K P Horn:

LISP, 3rd Edition

Addison--Wesley 1993

0-201-08319-1

Chapter 18.  LISP in LISP.

The chapter shows how to implement the LISP EVAL in Common LISP

itself.  Moreover, it presents the MICRO LISP, a simple variant of

LISP written in Common LISP.

I was planning to utilize that text in my C++ Shen project.

That was so, in particular, since the C++ is not as imperative as one

might assume -- it has the full scale recursion, and that Winston-Horn

CL EVAL, and CL MICRO LISP, can pretty straightforwardly be carried

over into the C++ language.

The best of success in your project:

yours, AJY

HELSINKI

The EU

[Mark Thom]

With all the functional features in C++ 1x, I don't think doing a raw interpreter would be that
hard to do -- convert to CPS, use trampolining for tail calls..

[Antti Ylikoski]

Quite so.

Moreover, the LLVM IR surely has good facilities for building the full scale recursion.  It would be weird if it did not have ones.

I hope you can do the Shen eval and the Shen macros from this research.  And how about reading the MACLISP DEFMACRO source code, or such?  Or, the Franz LISP DEFMACRO source?

yours, AJY

HELSINKI

The EU

[Mark Thom]

Oh, I meant doing an implementation in pure C++, no LLVM IR required.

But yes, I'm now convinced writing eval and macros in straight Shen shouldn't be too difficult.

[Antti Ylikoski]

OK I see.

What I had in mind, was that writing the Shen eval and the defmacro

would be doable in:

1) pure Shen, or;

2) C++/K-Lambda, or;

3) a system which outputs LLVM IR code, which IR code can easily

handle full scale recursion

based on the Winston-Horn LISP EVAL, and eg. the Franz LISP defmacro

source code.  (One can download the Open BSD VMUNIX, the Open Berkeley

Standard Distribution VMUNIX, from the site 

http://www.openbsd.org/)

I did not check whether this VMUNIX has the Franz LISP source, I think

it does have the source code.

yours, AJY

HELSINKI

The EU

[Mark Thom]

I wouldn't want to do defmacro in C++, let alone LLVM IR! Any kind of tree transformation
is a nasty, nasty thing to write in an imperative language.

[Antti Ylikoski]

OK, summa summarum you know better than do I.

I recall one American scientific text that read that the "trick" of intelligent behaviour somehow is contained in the idea of recursion.  Anyone who has written an intelligent algorithm in a recursive language has certainly seen that.

AJY

[Antti Ylikoski]

OK, summa summarum you know better than do I.

I recall one American scientific text that read that the "trick" of intelligent behaviour somehow is contained in the idea of recursion.  Anyone who has written an intelligent algorithm in a recursive language has certainly seen that.

AJY

2015-12-03 2:17 GMT+02:00 Mark Thom <markjor...@gmail.com>:

I wouldn't want to do defmacro in C++, let alone LLVM IR! Any kind of tree transformation
is a nasty, nasty thing to write in an imperative language.

--
You received this message because you are subscribed to a topic in the Google Groups "Shen" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/qilang/xSzROgts5fc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to qilang+un...@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at http://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

[deech]

There might be some inspiration here. https://github.com/drmeister/clasp.
-deech

[Mark Thom]

Yes, no doubt. That's how I first heard of MPS -- he's also using it for GC.

[Mark Thom]

You know, I think I'll try my hand at a straight C++ interpreter. I'll leave to tweak
MPS, and it'll calm my eval / macro expansion woes. Turtles all the way down.

[Raoul Duke]

Somebody crazy should target ATS to target c ;-)

http://www.ats-lang.org/

[Mark Thom]

Be my guest! ATS aims to be much much safer, and has better support for functional
programming on top of that.

[Raoul Duke]

Yup in my copious free time ;-) I am lame / overcommitted. So it is a daydream fantasy of mine. ATS has a flag to use Boehm–Demers–Weiser GC so that's be an "easy" start.

[Mark Thom]

If anyone wants to do an implementation of Felleisen's CESK machine in C++, I have the necessary components up on my github.

They could both use some polishing, but are useable:

1. https://github.com/mthom/on-the-fly-gc -- a concurrent mark sweep GC that already has very low pause times.

2. https://github.com/mthom/unmanaged-ctrie -- an implementation of concurrent hash tries, a fast, thread safe map abstraction
with constant time snapshots. Snapshots are implemented, iterators are not!

3. https://github.com/mthom/managed-ctrie -- a demo program merging the above two. Shows how to memory manage ctries with the GC.

If there's interest, I may write a series of small blog posts explaining the set up of the managed ctries -- how to interface with the
on-the-fly-gc, which is reasonably modular.

I wrote above, months ago, that I planned to write a CESK machine for Shen in C++. Those plans haven't changed, but lately
I've become more interested in Prolog implementation. Prolog implementation is one of the few areas where the
performance of Shen/SBCL can be challenged, after all, and I'd like much faster and more easily tunable type checking.

But these priorities might not be shared be the community, so I'd like to know what you'd all like to see. Is there
still interest in compiling to LLVM IR, for instance? Does anyone have a good stop the world GC with better
memory throughput and cache locality than my CMS GC?

[Raoul Duke]

I can't do anything with it, but it is cool. You should get it out on Show HN or something. :-)

[Mark Thom]

Thanks, it is cool. :) Something tells me it isn't flashy enough for Show HN.

[Raoul Duke]

Well LtU or something. Just to find like minded folks. Not to get upvoted into infamy. :-)

[Neal Alexander]

LLVM produces fast code with debug symbol support, but their JIT compilation time is really quite bad, even with no optimization passes enabled. 

I've been playing around with alternate code generation backends, for use at runtime only in eval-kl. Libjit was easy to adapt, but it looks like their tailcall support is broken, and the project seems fairly dead. 

I'm currently working on a GNU lightning interface, which seems to be in a better position, since its being used by CLISP, Racket, and GNU Smalltalk, but I haven't really come across any JIT libraries that I've been impressed with. It's a shame there don't seem to be any commercial offerings.

[Mark Thom]

This is the first I've ever heard of GNU lightning. Fascinating.  Does it let you tweak the passes on the assembly it puts out?

[Mark Thom]

It is available under any license other than GPL?

[Neal Alexander]

LGPL I think.


Lightning does very little - in particular, no register allocation. 

I'm curious how a minimal stack based VM implementation with Lightning will compare to other options. It probably puts a lot of pressure on the CPU cache from all the stack action, but I'm hoping its still faster than an optimized interpreter.

Anyway, the LLVM backend was generating code which was spilling registers quite a bit, and its register allocator does strange things sometimes.

[Raoul Duke]

Eh compile to js via emscripten and use V8.

(Sick joke.)