Simple Scheme, for Android

A simple implementation of a Schem-like Language and Editor for Android


Available in the Google Play Store.


The What and Why:

I was on the train, wanted to write some code, and I though, "I wonder if there are any good Scheme implementations for my phone?" I didn't find any that were simple, easy to use, and efficient (the first one I installed crashed my phone). I also wanted to be able to write graphical and interactive programs easily (see image examples and/or big-bang/interaction examples). So... I started an implementation of all the major features I could think of (see traditional Scheme forms and examples, and the apendix for the full list of supported functions).

The execution needed to be tail-recursive, and even non-tail-recursive functions shouldn't run out of stack space, so I implemented a continuation-passing style interpreter with efficient binding and lookup.

While I tried to remain faithful to the term "Scheme-like", I made a few changes to the language (and the implementation) to make it a little easier on myself. For the most part the changes are syntactic, e.g., the way that literals written and the use of square-brackets to group cond clauses and let definitions. (This is supported in Dr.Racket, but required in Simple Scheme).


Major Differences:

Traditional Language Forms, Features, Examples:

Like traditional Scheme, Simple Scheme supports define, define-struct, begin, let, and many other forms/expressions. Below are a few examples:

Simple stuff... 
;; Comments, of course, not executed
#|
    Multi-line Comment(s)
    These are not nested though
|#

;; Value definitions
(define two-pi (* 2 pi))
Function definitions... 
;; Factorial with IF
(define (fact n)
  (if (< n 2)
      1
      (* n (fact (- n 1)))))

(fact 5) ;; => 120

;; Factorial with COND
(define (fact-cond n)
  (cond [(< n 2) 1]
        [else (* n (fact (- n 1)))]))

(fact-cond 6) ;; => 720


;; Mutually-recursive top-level definitions
(define (even n)
   (or (= n 0) (not (odd n))))
(define (odd n)
   (or (= n 1) (even (- n 1))))

(even 5) ;; => false
(even 8) ;; => true
(odd 5)  ;; => true
(odd 8)  ;; => false
Structure definitions... 
;; Point: Number x Number
;; defines: make-point, point-x, point-y, and point?
(define-struct point (x y))

(define origin (make-point 0 0))
(define p (make-point 3 4))

(point? p)  ;; => true
(point-x p) ;; => 3
(point-y p) ;; => 4

;; Distance between two points
(define (distance p1 p2)
  (let ([dx (- (point-x p2) (point-x p1))]
        [dy (- (point-y p2) (point-y p1))])
    (sqrt (+ (* dx dx)
             (* dy dy)))))

(distance origin p) ;; => 5
Symbols...
Symbols are similar to String literals, but equlity comparison is much more efficient (symbol=? vs. string=?). That's pretty much it. 
;; Simple symbol literal
(define a-symbol 'symb)

;; Conversion and comparison
(symbol=? (string->symbol "test") 'test) ;; => true
(string=? (symbol->string 'test) "test") ;; => true
Lists...
Lists can be created three ways... cons/empty, list notation, or quote/' notation. 
;; Using cons and empty
(define a-b-c (cons 'a (cons 'b (cons 'c empty))))
;; Using list
(define one-two-three (list 1 2 3))
;; Using quote/'
(define mix-1 (quote (a (b) (1 2))))
(define mix-2 '(a (b) (1 2)))
Each notation can produce equivalent lists in these cases, though expressions within quote/' are not evaluated. 
;; These are equivalent
'((+ 2 3) (* 2 3))
(list (list '+ 2 3) (list '* 2 3))

;; And so are these
(list (+ 2 3) (* 2 3))
(list 5 6)
Of course we have lots of functions that operate on lists... 
(first '(1 2 3))      ;; => 1
(second '(1 2 3))     ;; => 2
(list-ref '(1 2 3) 2) ;; => 3

(list? a-b-c)  ;; => true
(empty? a-b-c) ;; => false
(cons? a-b-c)  ;; => true
(empty? (rest (rest (rest a-b-c)))) ;; => true

(length a-b-c)       ;; => 3
(append '(a b) '(c)) ;; => (list 'a 'b 'c)
(reverse a-b-c)      ;; => (list 'c 'b 'a)
Simple Scheme also includes map, foldr, foldl, and filter. 
(map (lambda (n) (* n n)) '(1 2 3 4))   ;; => '(1 4 9 16)
(foldr string-append "" '("a" "b" "c")) ;; => "abc"
(foldl string-append "" '("a" "b" "c")) ;; => "cba"

(filter odd? '(1 2 3 4))  ;; => '(1 3)
(filter even? '(1 2 3 4)) ;; => '(2 4)

(andmap odd? '(2 4 6))  ;; => false
(andmap even? '(2 4 6)) ;; => true
(ormap odd? '(2 4 6))   ;; => false
(ormap odd? '(4 5 6))   ;; => true
And, if you have others that are missing, you can either write them, or, if performance is important, request that I add them... e.g.: 
(define (map2 f xs ys)
  (cond [(or (empty? xs) (empty? ys)) empty]
	[else (cons (f (first xs) (first ys))
		    (map2 f (rest xs) (rest ys)))]))

(map2 + '(1 2 3 4) '(2 4 6 8)) ;; => '(3 6 9 12)
(map2 * '(1 2 3 4) '(2 4 6 8)) ;; => '(2 8 18 32)
Sequencing and misc stuff... 
;; Prints 'five: 5\n', produces 20
(begin (print "five: ") (println 5) (* 4 5))

;; Prints 'five: 5\n', produces 20
(begin0 (* 4 5) (print "five: ") (println 5))

;; Extra math functions: mod, [in/de]crement
(% 13 5) ;; => 3
(++ 5)   ;; => 6
(-- 5)   ;; => 4

;; Bitwise functions: or, and, xor, shifts
(| 0xA 3)  ;; => 11
(& 0xA 3)  ;; => 2
(^ 0xA 3)  ;; => 9
(>> 0xF 2) ;; => 3
(<< 0xF 2) ;; => 60

Values and Let-Values:

Values can be compound, and functions can return multiple values. But you need to unpack them with special let forms, i.e., let-values, let*-values, or letrec-values. 

(define (translate x y t)
  (values (+ x t) (+ y t)))

(define (scale x y s)
  (values (* x s) (* y s)))

(define (scale-&-translate x y s t)
  (let-values ([(nx ny) (scale x y s)])
    (translate nx ny t)))

(scale-&-translate 3 4 10 2) ;; => (values 32 42)

Simple Macros:

Simple Scheme supports a restricted form of macros via define-syntax. You can see what your program looks like after expansion with the new expand button. Macro expansion is not complete, and there are limited warnings/checks. I'm hoping to improve the syntax and features when I have time. 

(define-syntax foo-bar
  (syntax-rules ()
    [(foo-bar a) (+ a 2)]
    [(foo-bar a b) (* a b)]))

(foo-bar 1)    ;; Expands to (+ 1 2)
(foo-bar 2 20) ;; Expands to (* 2 20)

If you only have one case, you can shorten that with define-syntax-rule

(define-syntax-rule (add-to-all n lst)
  (map (lambda (m) (+ n m)) lst))

(add-to-all 5 (list 1 2 3)) ;; => (list 6 7 8)

You can't override keywords or standard forms, but you can have identifiers be considered symbols in pattern expressions (instead of binding names) 

(define-syntax do
  ;; add, sub, and mult are matched as literals instead of bindings
  (syntax-rules (add sub mult)
    [(do add a b) (+ a b)]
    [(do sub a b) (- a b)]
    [(do mult a b) (* a b)]))

(do add 2 4)   ;; Expands to (+ 2 4)
(do mult 5 10) ;; Expands to (* 5 10)
(do sub 7 5)   ;; Expands to (- 7 5)

But, you can use let and other bindings in your macros, and variables will be renamed to avoid scope conflicts. Youo can also have your macro refer to itself!. Warning: I cannot promise guarentee that you will always get what you want. If you find issues/oddities, please let me know and I'll fix them as soon as I can! :) 

;; Give this a try, and see what it expands to!
(define-syntax myor
  (syntax-rules ()
    [(myor a b c) (myor a (myor b c))]
    [(myor a b) (let ([aa a]) (if aa aa b))]))

(myor (< 5 6) (= 6 3))
(myor (< 4 7) (> 5 3) (= 2 8))

Image Functions and Examples:

I've implemented a library of functions and forms (similar to Racket's 2htdp/image and 2htdp/universe packages) that support the generation of images and even interactive games / animations.

First, colors are just strings that name a color or are specially formatted. A list of the supported named colors are listed here. In addition, we support '#' prefixed hex-colors with 3, 4, 6, or 8 digits. E.g., "red" = "#F00" = "#FF0000". For 4 and 8 digit colors, the first digit (digits) represent the color's alpha, or opacity. So "#F00F" is opaque blue, "#80F0" is partly clear green, and "#11FF0000" is almost completely clear red. Of course, these are mostly used when you begin to Overlay images... but let's start with some base images first.

Creating Simple Images... 
(circle 10 "solid" "#F00")                ;; red filled circle
(circle 20 "outline" "#00F")              ;; blue circle border
(ellipse 10 20 "solid" "#00FF00")         ;; green filled 10 x 20 ellipse
(ellipse 20 10 "outline" "#8F00")         ;; red, partly opaque 20 x 10 ellipse border
(rectangle 10 20 "solid" "#5500FF00")     ;; green, mostly clear, 10 x 20 rectangle
(square 10 "solid" "blue")                ;; blue 10 x 10 square
(triangle 20 "outline" "red")             ;; red triangle border with a radius of 20
(star 20 "solid" "green")                 ;; 5 pointed star, radius of 20
(star 20 7 "solid" "green")               ;; 7 pointed star, radius of 20
(star 20 10 7 "solid" "green")            ;; 7 pointed star, outer radius of 20, inner radius of 10
(text "Hello!" 30 "solid" "purple")       ;; purple text image, size 30 pts
(line 10 10 "yellow")                     ;; yellow 45 degree line
(round-rectangle 30 20 5 "outline" "gray")   ;; 30 x 20 rectangle with 5px round corners
(round-rectangle 30 20 6 4 "outline" "gray") ;; 30 x 20 rectangle with 6 x 4 ellipse corners
(polygon 20 6 "outline" "orange")         ;; orange hexagon outline of radius 20
(make-color 0xA0)                         ;; "#FFA0A0A0"
(make-color 32 48 64)                     ;; "#FF203040"
(make-color 16 32 48 64)                  ;; "#10203040"
Image properties... 
(image-width (square 20 "outline" "green"))   ;; => 20
(image-height (circle 20 "outline" "green"))  ;; => 40

Of course, these don't do much, until you can display them.. You can show your image(s) with (show-image img-value):

(show-image (star 200 9 "solid" "green"))

Overlays: You can overlay two (or more) images over the same center, or overlay/xy two images with the given x/y offsets (i.e., (overlay/xy top-img offset-x offset-y bot-img))

(show-image
   (overlay/xy (overlay (square 100 "solid" "#800F")
                        (square 200 "solid" "#8FFF")
                        (square 300 "solid" "#8F00"))
               0 310
               (overlay (circle 50 "solid" "blue")
                        (circle 100 "solid" "white")
                        (circle 150 "solid" "red"))))

Scenes: A Scene is a special kind of Image with its origin at the top-left. They can be created using empty-scene, and added to using place-image and/or add-line. The default color is "white", but you can also give the color as an argument.

Usually you just want an empty-scene the size of the currently running device screen.

;; 100x200 empty-scene, white
(empty-scene 100 200)
;; empty-scene (white) the size of the current device screen
(empty-scene)
;; 100x200 empty-scene, blue
(empty-scene 100 200 "blue")
;; empty-scene (black) the size of the current device screen
(empty-scene "black")

Once you have a Scene, you can place images, (place-image img x y scene), or add lines, (add-line scene x1 y1 x2 y2 color). Both functions return the resulting Scene 

;; Note: only the last show-image will really be
;;   displayed... so separate these when/if you run them
(show-image
  (place-image (triangle 120 "solid" "#8F00")
               300 100
               (place-image (square 120 "solid" "#800F")
                            200 100
                            (place-image (circle 50 "solid" "#80F0")
                                         100 100 (empty-scene)))))


(show-image 
  (add-line (add-line (add-line (empty-scene) 10 10 200 100 "blue")
                      10 10 200 200 "red")
            10 10 100 200 "green"))


Of course, you can write functions to generate Images and Scenes: 
(define (bulls-eye n x y radius)
  (if (= 0 n)
      (empty-scene)
      (place-image (circle radius "solid"
                           (if (= (% n 2) 0) "red" "gray"))
                   x y
                   (bulls-eye (- n 1) x y (+ radius 20)))))

(show-image (bulls-eye 8 275 400 30))



BigBang / Interactive Forms and Examples:

Along with the image functions, I've also implemented some of the features of Racket's big-bang form. Specifically, I have implemented:


The following program is a working big-bang example that uses a Number as the World, representing the Y coordinate of a moving dot.

  1. The World starts as the Number 0
  2. For on-draw, we create a Scene with a blue dot at the World height/y.
  3. For on-tick, we return an updated World, moving the dot down the screen by 5 pixels.
  4. For on-mouse, we set the World to be the height of the mouse/tap action.
;; The World is a Number that represents the Y-coord of a Dot
(define (draw-dot y)
  (place-image (circle 20 "solid" "blue")
               275 y
               (empty-scene)))

(big-bang 0
          (on-draw draw-dot)
          (on-tick (lambda (w) (+ 5 w)))
          (on-mouse (lambda (w x y what) y)))

If you run this example in Simple Scheme, the dot drifts toward the bottom of your screen. When you touch the screen, the dot is placed at the height of your tap.


A Bit More Complex...

We can scale up the previous example with a structure definition, and a more complicated tick function.

  1. The World starts at a point of (275,200), with a target point of (275,200)
  2. For on-draw, we create a Scene with a blue dot at the World X/Y.
  3. For on-tick, we return a new World, moving the dot a tenth of the way toward the target point. The function will be called every 0.03 seconds
  4. For on-mouse, we update the World's target point to the X/Y of the mouse/tap action. Possible values for the 4th argument to the on-mouse function are: "button-down", "drag", or "button-up"
;; The World is a Dot that represents the X/Y of a Dot
;;    and the X/Y of a Target point
(define-struct dot (x y tx ty))

;; Draw a Dot into an Empty-Scene
(define (draw-dot d)
  (place-image (circle 20 "solid" "blue")
               (dot-x d) (dot-y d)
               (empty-scene)))

;; Update the target point of the Dot
(define (mouse d x y what)
  (cond [(string=? what "button-down")
         (make-dot (dot-x d) (dot-y d) x y)]
        [else d]))

;; Move the Dot towards the target point
(define (step d)
  (make-dot (+ (dot-x d) (/ (- (dot-tx d) (dot-x d)) 10.0))
            (+ (dot-y d) (/ (- (dot-ty d) (dot-y d)) 10.0))
            (dot-tx d)
            (dot-ty d)))

(big-bang (make-dot 275 200 275 200)
          (on-draw draw-dot)
          (on-tick step 0.03)
          (on-mouse mouse))

If you run this example in Simple Scheme, when you tap the dot will drift toward where you tap... quickly at first, then slowing down.


Using Device Orientation Events...

As a final example, we'll use Simple Scheme's connection to your Android device's orientation/accelerometer events to affect your Worlds.

This one's also a little more general, so it will look good on your device(s) too :)

  1. The World starts with a zero direction
  2. For on-draw, we create a Scene with a line from the center (width/2, height/2) in the direction of the last orientation X/Y
  3. For on-orient, we capture the X and Y orientation of the device. The the Y direction is correct because of the inversion of screen coordinates... but the X needs to be inverted.
(define-struct dir (x y))

(define scn (empty-scene))
(define width/2 (/ (image-width scn) 2))
(define height/2 (/ (image-height scn) 2))

;; Draw a line from the center 
(define (draw-line w)
  (add-line scn width/2 height/2
            (+ width/2 (* 20 (dir-x w)))
            (+ height/2 (* 20 (dir-y w)))
            "blue"))

(define (orient w x y z)
  (make-dir (- x) y))

(big-bang (make-dir 0 0)
          (on-draw draw-line)
          (on-orient orient))

If you run this example in Simple Scheme and move your device around, you should see the line point down (towards the ground), with a length that's proportional to how un-level the device is.

Hopefully that gives you enough to start messing with things... let me know if you find any errors/typos in the examples.

Enjoy!




Appendix: Full List of Supported Functions

Below is a list of all the currently supported operators with a brief description. For most operators, passing a double (decimal number) as any argument rasies the result to a non-integer result. Many of the primitives accept any number of 1 or more arguments, e.g., (- 6 3 1) is 2.

Below is a list of all the currently supported base functions with a brief description.