antiloquax
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

lisp and scheme

Mon Jul 30, 2012 10:30 pm

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
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Re: lisp and scheme

Thu Aug 02, 2012 1:45 pm

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
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: lisp and scheme

Thu Aug 02, 2012 4:06 pm

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
Posts: 321
Joined: Sun Sep 25, 2011 1:25 am

Re: lisp and scheme

Thu Aug 02, 2012 9:56 pm

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
Posts: 321
Joined: Sun Sep 25, 2011 1:25 am

Re: lisp and scheme

Thu Aug 02, 2012 10:31 pm

[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
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Re: lisp and scheme

Fri Aug 10, 2012 7:13 am

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.

User avatar
jackokring
Posts: 816
Joined: Tue Jul 31, 2012 8:27 am
Location: London, UK
Contact: ICQ

Re: lisp and scheme

Fri Aug 10, 2012 8:03 am

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. :D

Cheers Jacko
Pi[NFA]=B256R0USB CL4SD8GB Raspbian Stock.
Pi[Work]=A+256 CL4SD8GB Raspbian Stock.
My favourite constant 1.65056745028

tufty
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: lisp and scheme

Sat Aug 11, 2012 6:26 am

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
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: lisp and scheme

Sat Aug 11, 2012 6:49 am

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
Posts: 321
Joined: Sun Sep 25, 2011 1:25 am

Re: lisp and scheme

Sat Aug 11, 2012 7:07 am

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
Posts: 65
Joined: Sat Jul 07, 2012 11:21 pm
Location: Zero Page

Re: lisp and scheme

Sat Aug 11, 2012 9:17 am

tufty wrote: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
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Re: lisp and scheme

Sat Aug 11, 2012 12:53 pm

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
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: lisp and scheme

Sun Aug 19, 2012 8:12 pm

Bakul Shah wrote: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
Posts: 321
Joined: Sun Sep 25, 2011 1:25 am

Re: lisp and scheme

Sun Aug 19, 2012 8:46 pm

tufty wrote: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
Posts: 406
Joined: Sun Nov 20, 2011 11:37 am
Contact: Website

Re: lisp and scheme

Fri Aug 24, 2012 7:25 pm

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.
Image

Return to “Other programming languages”