[racket] Compiler for despair 1

From: Eduardo Costa (edu500ac at gmail.com)
Date: Fri Oct 31 22:47:18 EDT 2014

I tried to implement despair 1 in Racket, and have a few questions about my
solution. By the way, I am not a student trying to get my homework done by
somebody else.

The restrictions for despair 1 are:

1 - The whole implementation must have less than 100 lines. Comments and
tests don't count as lines

2- No line should be longer than 30 chars

3- No function should have more than 12 lines

4- A blank line after each function is mandatory

5- The implementation can be done in any language and must pass despair
stOne.dsp


Here are two functions from stOne.dsp:

def (fib n (f-1 1) (f-2 1))
  if [n<2] then f-1
  else (fib [n - 1]
        [f-1+f-2] f-1)
  end
end

def (fibo n)
 let loop
   local (i n) (a 1) (b 1)//
   cond
    ift [i<2] then a//
    otherwise
      (loop [i - 1] [a+b] a)//
   end
 end
end

My question is about the Implementation of the infix to prefix function. My
 pref macro consumed almost half of the allowed number of lines. The
algorithm used is described in Lisp by Winston and Horn, third edition,
chapter 32. Is there a way to reduce the size of the pref macro (perhaps
changing the algorithm)?

In order to keep the (p e o a) function in the 12 lines limit, I was forced
to move the w? predicate out of (p e o a). Since Racket match requires one
parameter predicates, (w? e) returns a closure. My question is: Does Racket
rebuilds the closure for each iteration of (p e o a)? If this is the case,
the algorithm is very inefficient. I hope that Racket somehow builds the
closure just once. Thanks in advance for any piece of information or
suggestion on how to improve the program.

Special thanks to any member of this group who could tell me how to
transform my implementation into  #lang despair (no need to maintain the
restriction of 100 lines). By the way, I tried to understand the chapter
about building new language in the Racket documentation, but it still
puzzles me.

;File: pref.rkt
#lang racket
(require (for-syntax racket))
(provide pref)

(define-for-syntax(w s)
 (case s ;10 lines
  [(or) 1] [(and) 2]
  [(< = > >= <=) 3]
  [(+ -) 4] [(* /) 5]
  [(^) 6][(:) 7]
  [else 9]))

(define-for-syntax(:? x)
  (= (w x) 9))

 (define-for-syntax(w? e)
   (lambda(x)
     (> (w (car e))(w x))))

(define-for-syntax(pre x)
  (if (pair? x)
    (p (cdr x) '()
       (list (pre (car x))) )
      x))

(define-for-syntax(p e o a)
 (match/values (values e o a)
  [('() '() (cons x _)) x]
  [[(cons (? :?) _) _ _ ]
   (p (cons ': e) o a)]
  [[(list-rest x y es) (or
      '()  (cons (? (w? e))_))_]
   (p es (cons x o)
      (cons (pre y) a))]
  [[_ (cons c os)
      (list-rest x y r)]
   (p e os (f c y x r) )]))

(define-for-syntax(f c y x r)
  (if (equal? ': c)
      (cons (list y x) r)
      (cons (list c y x) r)))

(define-syntax(pref s)
 (datum->syntax s (pre
   (cdr (syntax->datum s)))))


;File: despair.rkt
#lang racket
(require (for-syntax racket))
(require "inf.rkt")

(define-for-syntax(brk x)
 (regexp-match*
  (regexp (~a "\"[^\"]+\"|"
      "#t|#f|[a-z]+->[a-z]+|"
      "[a-z?A-Z~-]+[0-9-]*|"
      "-?[0-9]+\\.?[0-9]*|"
      "<=|>=|//|"
      "[][()'&;*:<>=,+/^-]")) x))

(define-for-syntax (fix x)
  (match x
    ["def" "(define"]
    ["if" "(if"]
    ["then" ""]
    ["else" ""]
    ["end" ")" ]
    ["//" ")"]
    ["cond" "(cond"]
    ["ift" "("]
    ["let" "(let"]
    ["local" "("]
    ["otherwise" "(else"]
    ["[" "(pref"]
    ["]" ")"]
    [head head]))

(define-for-syntax (prs xpr)
  (with-input-from-string
    (string-join (for/list
       [(token (brk xpr))]
       (fix token)) " ")
    (λ() (read)) ))

(define-for-syntax(tkn stx)
  (~a "(" (file->string (cadr
     (syntax->datum stx)))
      ")"))

(define-syntax(ld stx)
 (datum->syntax stx
   (cons 'begin
     (prs (tkn stx)) )))

(ld "stOne.dsp")
(fibo 5)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20141101/8f378a5f/attachment-0001.html>

Posted on the users mailing list.