Register Machine

The machine details could be found in the SICP chapter 5. See here.

Instruction Summary

; access the register contents
(reg <register-name>)
; a constant value
(const <constant-value>)
; a control label
(label <label-name>)
; test a condition and jump to the control label
(test (op <operation-name>) <input_1> ... <input_n>)
(branch (label <label-name>)) ; only jump if the preceded test passes
; go to label immediately
(goto (label <label-name>))
; or go to label holds in the register
(goto (reg <register-name>))
; perform an operation
(perform (op <operation-name>) <input_1> .. <input_n>)
; assignment
(assign <register-name> (reg <register-name>))
(assign <register-name> (const <constant-value>))
(assign <register-name> (op <operation-name>) <input_1> .. <input_n>)
(assign <register-name> (label <label-name>))
; instructions to use the stack
(save <register-name>)
(restore <register-name>)

Valid kinds of constant value:

• (const 123) is the number 123,
• (const 1.23) is the float point number 1.23,
• (const "abc") is the string "abc",
• (const abc) is the symbol abc,
• (const (a b c)) is the list (a b c),
• and (const ()) is the empty list.

Machines

Machine	Details	Code
Fibonacci	See Section 5.1.4 and Figure 5.12	fibonacci.rs
GCD V1	See Section 5.1.1	gcd.rs
GCD V2	See Figure 5.4	gcd_v2.rs
GCD V3	See Figure 5.5 and Figure 5.6	gcd_v3.rs
Factorial	See Exercise 5.1 and Exercise 5.2	factorial.rs
Recursive Factorial	See Section 5.1.4 and Figure 5.11	recursive_factorial.rs
Newton V1	See Exercise 5.3 and Section 1.1.7	newton.rs
Newton V2	See Exercise 5.3 and Section 1.1.7	newton_v2.rs
Iterative Exponentiation	See Exercise 5.4	iterative_exp.rs
Recursive Exponentiation	See Exercise 5.4	recursive_exp.rs
The Explicit-Control Evaluator	See Section 5.4 and controller.scm	main.rs

Running

$ git clone https://github.com/Pagliacii/sicp-reg-machine
$ cd sicp-reg-machine
# List all machines
$ ls examples
# Running machine
$ cargo run --example <machine-name>

Exercise 5.51

Develop a rudimentary implementation of Scheme in C (or some other low-level language of your choice) by translating the explicit-control evaluator of Section 5.4 into C. In order to run this code you will need to also provide appropriate storage-allocation routines and other run-time support.

The Explicit-Control Evaluator

See 5.4 The Explicit-Control Evaluator for more details.

Play with it

$ cargo run --example ec_evaluator
    Finished dev [unoptimized + debuginfo] target(s) in 0.06s
     Running `target/debug/examples/ec_evaluator`

;;; EC-Eval input:
(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1)) n)))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

;;; EC-Eval input:
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* product counter) (+ counter 1))))
  (iter 1 1))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

;;; EC-Eval input:
(define (append x y)
  (if (null? x) y (cons (car x) (append (cdr x) y))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(append '(a b c) '(d e f))

;;; EC-Eval value:
(a b c d e f)

;;; EC-Eval input:
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(fib 5)

;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)

;;; EC-Eval value:
8

;;; EC-Eval input:
(exit)

Enable debug logging

# output to stderr
$ RUST_LOG=debug cargo run --example ec_evaluator
# redirect to a file. *Note*: direct writes to a file can become a bottleneck due to IO operation times.
$ RUST_LOG=debug cargo run --example ec_evaluator 2> /path/to/log/file

Currently supports syntax

; number
1
1.2
; boolean
true
false
;; or
#t
#f
; string
"hello"
"hi"
"123"
; symbol
'hello
'hi
; list
(list 1 2 3 4)
'(1 2 3 4)
'(a b c)
'()
; manipulate pair
(define p (cons 1 2))
(car p) ; => 1
(cdr p) ; => 2
; primitive procedures*
(+ 1 1)
(- 1 1)
(* 2 1.5)
(/ 1 2)
; definition
;; define a variable
(define a 1)
;; define a procedure
(define (inc x) (+ x 1))
; access and assignment
a
(set! a 2)
a
; if statement
(if (> a 1) (display "fizz") (display "buzz"))
;; or without else branch
(if (< a 1) (display "without else"))
; lambda statement
(lambda (a b) (if (> a b) (display "a")))
; sequence statements
(begin (define a 1)
       (set! a 2)
       (if (> a 1) (display "hello")))
; call a procedure
(+ 1 1)
(inc 2)
((lambda (a b) (if (> a b) (display "a"))) 2 1)
; `cond` statement
(cond ((= a 1) (display "Apple")  (newline))
      ((= a 2) (display "Banana") (newline))
      ((= a 3) (display "Cherry") (newline))
      (else    (display "Oops")   (newline)))
;; `cond` in procedure definition
(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) 0)
        (else (+ x))))
; logical composition operations
(and #t #t #t)    ;; zero or more arbitrary arguments
(or #f #f #f #f)  ;; zero or more arbitrary arguments
(not #f)          ;; requires exactly 1 argument
; `let` statement, a syntactic sugar
(let ((a 1) (b 2) (c 3))
  (display (+ a b c)))
; `let*` statement, a syntactic sugar
(let* ((x 3) (y (+ x 2)) (z (+ x y 5)))
  (* x z))
; "Named `let`" statement: `(let <var> <bindings> <body>)`
(define (fib n)
  (let fib-iter ((a 1)
                 (b 0)
                 (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))
(fib 50) ; => 12586269025

Note:

1. See primitive.rs for more primitive procedures.

2. cond Statement Details:

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

• Sam Scott - Building a runtime reflection system for Rust 🦀️
• Michael-F-Bryan - How could I implement a more accurate comparison?
• H2CO3 - How to use a HashMap to store a struct method?
• Geoffroy Couprie - Geal/nom
• code and bitters - Learning Rust: Let's Build a Parser!
• 2e71828 - How to import a trait defined at another file inside a macro?