; sometimes this returns something, sometimes it returns null
; have to watch those set!s: where's our type checker?
(define first-try:split-by
(letrec ((acc null)
(foo (lambda (splitter exp)
(cond ((null? exp) acc)
(#t (begin
(set!
acc
(append (list (car exp))
(foo splitter
(cdr exp))))
acc))))))
foo))
; watch what's going on with the append
; another case that would have been quickly caught by ML's type
; checking
(define (another-try:split-by splitter expression)
(letrec ((g
(lambda (littleList exp)
(if (null? exp)
(list littleList)
(let ((head (car exp)))
(if (eqv? (car exp) splitter)
(if (null? littleList)
(g null (cdr exp))
(cons littleList
(g null (cdr exp)))
)
(if (null? littleList)
(g head (cdr exp))
(g (append (list littleList)
head)
(cdr exp))
)
)
)
)
)))
(g null expression)))
;; debug the next three functions with the display put in the third
(define (contains? haystack needle)
(cond ((null? haystack) ()) ;; here's the bug
((eqv? needle (car haystack))
#t)
(#t (contains? (cdr haystack)
needle))))
(define (split-by x expr)
(letrec ([inner
(lambda (x expr lst curr)
(cond ((null? expr) (append lst (list curr)))
((eq? (car expr) x)
(inner x (cdr expr)
(append lst (list curr)) null))
(#t (inner x (cdr expr) lst
(append curr (list (car expr)))))))])
(inner x expr null null)))
(define (infix->prefix expr)
(cond ((not (list? expr)) expr)
((null? (cdr expr)) (infix->prefix (car expr)))
(#t
(let ((apply-op
(lambda (op expr)
;; this display is a good way to trace
;; your code for debugging. Remember that
;; a lambda statement can contain multiple
;; expressions (lambda (args) exp1
;; exp2...), that's why we don't have to
;; use a (begin ...)
(display (list op expr)) (newline)
(if (contains? expr op)
(cons op
(map infix->prefix
(split-by op expr)))
expr))))
(foldl apply-op expr '(+ - * /))))))
;; Some DysFun functions
(define fact-dys '(
func fact (n) {
x := 1 !
while (n > 1) {
x := n * x !
n := n - 1 !
} !
return x !
}
))
(define min-dys '(
func min (a,b) {
if (a < b) {
return a !
} else {
return b !
} !
display("Shouldn't be here") !
}
))
;; A DysFun function with its translation
'(func foo(x,y) { z := x + y ! w := z - x ! return (z + w)!})
;; translates to the following (anything equivalent is okay)
(lambda (x y)
(let/cc return
(let ((z (void))
(w (void)))
(begin
(set! z (+ x y))
(set! w (- z x))
(return (+ z w))))))
;; If we enclosed the above in (letrec ((foo ...)) foo), then we
;; could have recursive functions, but that's not necessary for
;; this assignment (and it would conflict with the 2nd extra
;; credit).
;; Macros, if we have time to get to this
;; Some of this is advanced stuff that we don't expect you to know
;; A simple macro
(define-syntax let1
(syntax-rules ()
[(let1 (x b) expr)
(let ((x b)) expr)]))
(let1 (x 8) (+ 7 x))
;; A macro with repeated elements
(define-syntax while
(syntax-rules ()
[(while cond exp ...)
(letrec ((loop
(lambda ()
(if cond
(begin
exp ...
(loop))))))
(loop))]))
(let1 (x 0) (while (< x 6)
(display x)
(newline)
(set! x (+ 1 x))))
;; Repetition can be complex
;;
;; The ... in the (begin) matches with exp, and the entire
;; enclosing expression of exp to ... is repeated. So one (let)
;; for each exp in the display-while.
(define-syntax display-while
(syntax-rules ()
[(display-while cond exp ...)
(letrec ((loop
(lambda ()
(if cond
(begin
(let ((x exp))
(begin (display x)
(newline)))
...
(loop))))))
(loop))]))
(let1 (now (current-seconds))
(display-while (< (current-seconds) (+ now 10))
(begin
(let1 (x 0) (while (< x 1000000)
(set! x (+ 1 x))))
(current-seconds))))
;; A macro with multiple patterns
(define-syntax for
(syntax-rules (in to step)
[(for i in lo to hi exp)
(letrec ((loop
(lambda (i)
(if (<= i hi)
(begin
exp
(loop (+ 1 i)))))))
(loop lo))]
[(for i in lo to hi step s exp)
(letrec ((loop
(lambda (i)
(if (<= i hi)
(begin
exp
(loop (+ s i)))))))
(loop lo))]))
(for i in 1 to 10 (begin (display i) (newline)))
;; Because the macros are hygenic it's safe to use s
(for s in 1 to 10 step 2 (begin (display s) (newline)))
;; Note there are other ways to do macros in lisp-like
;; languages that you may see a lot (e.g. elisp), like
;; define-macro or defmacro, that are more literally
;; constructive and use quasiquote to build up lists, much
;; like our DysFun->Scheme translator. I won't get in to
;; them but advanced students might want to know they're out
;; there.