;;;; Unlambda interpreter

(defun evaluate (expr)
  (do (res (curc nil) (stk `((ev ,@expr))))
      ((null stk) res)
    (setf
     (values stk res)
     (case (caar stk)
       ((ev)
        (if (consp (cadar stk))
            `((ev ,@(caadar stk)) (ev1 ,@(cdadar stk)) ,@(cdr stk))
          (values (cdr stk) (cdar stk))))
       ((ev1)
        (if (eq (car res) 'd)
            (values (cdr stk) `(d1 ,@(cdar stk)))
          `((ev ,@(cdar stk)) (ap ,@res) ,@(cdr stk))))
       ((ap)
        (let ((a (cdar stk)) (cnt (cdr stk)))
          (case (car a)
            ((k)  (values cnt `(k1 ,@res)))
            ((k1) (values cnt (cdr a)))
            ((s)  (values cnt `(s1 ,@res)))
            ((s1) (values cnt `(s2 ,(cdr a) ,@res)))
            ((s2) `((ev (((,(cadr a) ,@res)) (,(cddr a) ,@res))) ,@cnt))
            ((i)  (values cnt res))
            ((v)  (values cnt a))
            ((e)  (values nil res))
            ((c)  `((ev (,res c1 ,@cnt)) ,@cnt))
            ((c1) (values (cdr a) res))
            ((d1) `((ev (,(cdr a) ,@res)) ,@cnt))
            ((at) (setq curc (read-char *standard-input* nil))
                  `((ev (,res ,(if curc 'i 'v))) ,@cnt))
            ((dt) (write-char (cdr a)) (values cnt res))
            ((qu) `((ev (,res ,(if (eql curc (cdr a)) 'i 'v))) ,@cnt))
            ((pi) `((ev (,res ,@(if curc `(dt ,@curc) '(v)))) ,@cnt))
            ((sl) `((ev (,res ,@(if curc `(qu ,@curc) '(v)))) ,@cnt)))))))))

(defun parse ()
  (ecase (char-downcase
	  (loop (let ((c (read-char)))
		  (if (eql c #\#) (read-line)
		    (or (member c '(#\Space #\Newline #\Tab #\Return))
			(return c))))))
    ((#\`) `((,(parse) ,@(parse))))
    ((#\k) '(k))
    ((#\s) '(s))
    ((#\i) '(i))
    ((#\v) '(v))
    ((#\c) '(c))
    ((#\d) '(d))
    ((#\e) '(e))
    ((#\@) '(at))
    ((#\|) '(pi))
    ((#\/) '(sl))
    ((#\r) '(dt . #\Newline))
    ((#\.) `(dt ,@(read-char)))
    ((#\?) `(qu ,@(read-char)))))

(evaluate (prog1 (parse) (read-line *standard-input* nil)))