lisp and scheme

[antiloquax]

I am starting to learn a bit of scheme and maybe lisp as well. I've seen that common lisp and guile are available in the arch repo. However, I have been using MIT scheme on my other Linux boxes. Does anyone have any experience with guile? Is it worth switching to that?

[antiloquax]

Also interested in Dr Racket - a nice IDE for Scheme. I haven't tried to build it on my Pi yet. May have a go this afternoon.
mark

[tufty]

I'm personally rather fond of ypsilon. Tinyscheme is pretty good too, only r5rs but none the worse for that, and it's the base for extempore, which might be convinced to run on the pi with some hacking now llvm has a decent arm backend.

[Bakul Shah]

Lots of choices here. I don't like guile but over time I have used scm (what guile is based on), gambit, ypsilon, s9, racket, chibi-scheme, ikarus, gauche etc. A number of these have an arm port. Stick to the r5rs subset and you'd be fine with most. You can also use slib (scheme library) for some common libraries.

Extempore is not quite Scheme anymore.

[Bakul Shah]

[Meant to add this to the last post but the edit window closed!]

Extempore is not quite Scheme anymore. I believe there is an associated interpreted Scheme but Extempore itself is statically typed.

As for a Scheme compiler, I think that for a small machine such as the raspi, Ken Thompson's approach to the plan9 c compilers might be better. Nils Holm (author of s9) in his "Practical Compiler Construction" book uses a similar minimalist approach to code generation. The book has a complete compiler for a C subset, about 4300 lines of C code. Ken's compilers are bigger but they implement close to a standard C and generate decent code (and compile in a fraction of the time gcc takes).

[antiloquax]

Thanks for those replies. I still haven't gone any further than using Guile on the Pi. I tried to build MIT Scheme from the "Portable C" source code, but got errors and so gave up!

If anyone out there is interested in learning Scheme, there is an excellent series of lectures by Harold Abelson and Gerald Jay Sussman: YouTube Videos.

Their well-known book, "The Structure and Implementation of Computer Programs" (on which this lecture course is based) is also available free online. MIT Press.

[jackokring]

Developing a list based language called ScriptLanguage embedded in jarvar (a simplified idea for fewer java classes) as link in my signature. I have been interested in lisp/scheme as an expression tool. The use of square brackets has more options for embedding in python lists... and maybe I can hijack some IO routines to experiment.

Cheers Jacko

[tufty]

As far as building compilers for scheme goes:

SICP, as pointed out by Bakul
'Let's build a compiler' by Crenshaw (pascal compiler, but relevant)
Abdulaziz Ghuloum's work
'Compiling with continuations'
'90 minute scheme to C compiler'

Simon

[tufty]

I apologise for the lack of links in the previous post, posting from crapdroid makes it painful. Google should elucidate...

Here's what I'm doing (not currently available, soon, I promise)

- CPS conversion of input code, allows high level optimisations.
- Ghuloum-style compiler to a proto-assembly, still in scheme.
- Proto-assembly to assembly source conversion

And then pump the output into your targetted assembler.

The first step is basically optional, but useful from an optimisation point of view.
The second, compiling to raw assembly, is the easiest approach for a first time compiler writer, and can be elaborated to include the first step later. However, adding the last step allows target level optimisations - register allocation optimisations and so on - as well as platform (or assembler) retargetting - as the source is still scheme we can still reason about it. This may or may not relate to my comment on Herman's thread ;)

Bviously the last bit, actual assembly, should be done with a scheme-based assembler in order to be self-hosting.

Simon

It's not a trivial job, but it's more than manageable.

[Bakul Shah]

This page is a great resource on Scheme implementation techniques. I should also mention Lisp in Small Pieces

Looking forward to your compiler, Simon!

[hermanhermitage]

As far as building compilers for scheme goes:
SICP, as pointed out by Bakul
'Let's build a compiler' by Crenshaw (pascal compiler, but relevant)
Abdulaziz Ghuloum's work
'Compiling with continuations'
'90 minute scheme to C compiler'

Not for scheme, but I'm a huge fan of http://www.amazon.com/Advanced-Compiler ... 1558603204. Its invaluable reference for anyone building compilers and JITs. Not a beginners book by any means but its terrific!

[antiloquax]

At the moment, my favourite implementation is mit-scheme.
I have tried to install this on my Pi, using the native C source files. However, when I try to build it, I get an error message to do with a file called confshared.h.
If anyone has managed to do this and/or can help me out, I'd be very grateful.
mark

[tufty]

This page is a great resource on Scheme implementation techniques. I should also mention Lisp in Small Pieces

Looking forward to your compiler, Simon!

Getting there. Still beating my head around register allocation (I'm implementing linear scan, the theory is simple but shoehorning it into the compiler is hard - it's b0rked at the moment) so the following code does a whole load of register spilling and unspilling instead and is therefore "a bit" inefficient.

Code: Select all

(lambda (x y)
  (if (< x #xfeedface)
      (cons x (cons y '()))
      (cons y '())))

generates:

Code: Select all

(((stm db !) sp (r0-12 lr))
 ((mov) fp sp)
 ((sub) sp -4)
 ((ldr) r0 (fp 64))
 ((str) r0 (fp -4))
 ((ldr) r0 "L_3")
 ((ldr) r10 (fp -4))
 ((cmp) r0 r10)
 ((msr ge) apsr_nzcvq 0)
 ((msr lt) apsr_nzcvq 1073741824)
 ((b ne) "L_4")
 (label "L_0")
 ((ldrex) r0 (r9))
 ((add) r0 r0 8)
 ((strex) r10 r0 (r9))
 ((teq) r10 0)
 ((b ne) "L_0")
 ((orr) r0 r0 1)
 ((str) r0 (fp -4))
 ((ldr) r0 (fp 64))
 ((ldr) r10 (fp -4))
 ((str) r0 (r10 -1))
 (label "L_1")
 ((ldrex) r0 (r9))
 ((add) r0 r0 8)
 ((strex) r10 r0 (r9))
 ((teq) r10 0)
 ((b ne) "L_1")
 ((orr) r0 r0 1)
 ((str) r0 (fp -8))
 ((ldr) r0 (fp 60))
 ((ldr) r10 (fp -8))
 ((str) r0 (r10 -1))
 ((movw) r0 1151)
 ((ldr) r10 (fp -8))
 ((str) r0 (r10 3))
 ((mov) r0 r10)
 ((ldr) r10 (fp -4))
 ((str) r0 (r10 3))
 ((mov) r0 r10)
 ((b) "L_5")
 (label "L_4")
 (label "L_2")
 ((ldrex) r0 (r9))
 ((add) r0 r0 8)
 ((strex) r10 r0 (r9))
 ((teq) r10 0)
 ((b ne) "L_2")
 ((orr) r0 r0 1)
 ((str) r0 (fp -4))
 ((ldr) r0 (fp 60))
 ((ldr) r10 (fp -4))
 ((str) r0 (r10 -1))
 ((movw) r0 1151)
 ((ldr) r10 (fp -4))
 ((str) r0 (r10 3))
 ((mov) r0 r10)
 (label "L_5")
 ((add) sp -4)
 ((ldm ia) sp (r0-12 pc))
 (label "L_3")
 (word 34216072816))

[Bakul Shah]

Getting there. Still beating my head around register allocation (I'm implementing linear scan, the theory is simple but shoehorning it into the compiler is hard - it's b0rked at the moment) so the following code does a whole load of register spilling and unspilling instead and is therefore "a bit" inefficient.

Is something like BURG (Bottom Up tree Rewriting code generator Generator) of any use? IIRC, lcc's backend uses it. Don't know if there is a Scheme implementation of BURG.

Are you using SSA? Wimmer & Franz's paper on linear scan allocation on SSA form seems interesting.

[antiloquax]

Just learning some bits of Scheme at the moment. Here's a little program that I wrote from scratch. You give it an integer and it hands you back a list of random numbers between 1 and 12.

Code: Select all

; get_nums. Takes an integer and returns a list of that length,
; populated with random numbers (1 - 12)

(define (get_nums i)
  (cond
      ((= i 0) '())
      (else (cons (+ 1 (random 12)) (get_nums (- i 1))))))

Here's a sample output.