This repository has been archived on 2022-08-10. You can view files and clone it, but cannot push or open issues or pull requests.
chez-openbsd/examples/edit.ss

465 lines
20 KiB
Scheme
Raw Permalink Normal View History

2022-07-29 15:12:07 +02:00
;;; edit.ss
;;; Copyright (C) 1987 R. Kent Dybvig
;;; Permission is hereby granted, free of charge, to any person obtaining a
;;; copy of this software and associated documentation files (the "Software"),
;;; to deal in the Software without restriction, including without limitation
;;; the rights to use, copy, modify, merge, publish, distribute, sublicense,
;;; and/or sell copies of the Software, and to permit persons to whom the
;;; Software is furnished to do so, subject to the following conditions:
;;;
;;; The above copyright notice and this permission notice shall be included in
;;; all copies or substantial portions of the Software.
;;;
;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
;;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
;;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
;;; THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
;;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
;;; FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
;;; DEALINGS IN THE SOFTWARE.
;;; This file contains an implementation of a simple interactive structure
;;; editor for Scheme. The editor is invoked with an expression as it's
;;; single argument. It prompts for, reads, and processes editor commands.
;;; The editor commands recognized are those documented in the Texas
;;; Instruments' PC Scheme manual. They are summarized below.
;;; Command syntax Action
;;;
;;; q or <eof> Quit the editor, returning edited expression.
;;;
;;; p Write the current expression.
;;;
;;; ? Write to level 2, length 10.
;;;
;;; pp Pretty print the current expression.
;;;
;;; ?? Pretty print to level 2, length 10.
;;;
;;; <pos> Move to subexpression of current expression
;;; <pos> = 0 is the current expression, <pos> > 0
;;; is the numbered subexpression (1 for first, 2
;;; for second, ...), <pos> < 0 is the numbered
;;; subexpression from the right (-1 for last, -2
;;; for second to last, ...), and <pos> = * is the
;;; "last cdr" of the current expression. If <pos>
;;; is not 0, the current expression must be a list.
;;;
;;; b Move back to parent expression.
;;;
;;; t Move to top-level expression.
;;;
;;; pr Move to expression on the left (previous).
;;;
;;; n Move to expression on the right (next).
;;;
;;; (f <obj>) Find <obj> within or to the right of the current
;;; expression using equal?.
;;;
;;; f or (f) Find <obj> of last (f <obj>) command.
;;;
;;; (d <pos>) Delete the expression at position <pos>.
;;;
;;; (r <pos> <obj>) Replace the expression at position <pos> with
;;; <obj>.
;;;
;;; (s <obj1> <obj2>) Replace all occurrences of <obj1> by <obj2>
;;; within the current expression.
;;;
;;; (dp <pos>) Remove parens from around expression at position
;;; <pos>.
;;;
;;; (ap <pos1> <pos2>) Insert parens around expressions from position
;;; <pos1> through <pos2> (inclusive). If <pos1> is
;;; 0 or *, <pos2> is ignored and may be omitted.
;;;
;;; (ib <pos> <obj>) Insert <obj> before expression at position <pos>.
;;;
;;; (ia <pos> <obj>) Insert <obj> after expression at position <pos>.
;;;
;;; (sb <pos> <obj>) Splice <obj> before expression at position <pos>.
;;;
;;; (sa <pos> <obj>) Splice <obj> after expression at position <pos>.
;;; Possible exercises/enhancements:
;;;
;;; 1) Implement an infinite undo ("u") command in the editor. This
;;; can be done by creating an "inverse" function for each operation
;;; that causes a side-effect, i.e, a closure that "remembers" the
;;; list cells involved and knows how to put them back the way they
;;; were. An undo (u) variable could then be added to the editor's
;;; main loop; it would be bound to a list containing the set of
;;; registers at the point of the last side-effect (similarly to the
;;; "back" (b) variable) and the undo function for the side-effect.
;;;
;;; 2) Implement an infinite redo ("r") command in the editor. This
;;; can be done by remembering the undo functions and registers for
;;; the undo's since the last non-undo command.
;;;
;;; 3) Handle circular structures better in the editor. Specifically,
;;; modify the find ("f") command so that it always terminates, and
;;; devise a method for printing circular structures with the "p"
;;; and "pp" commands. Cure the bug mentioned in the overview of
;;; the code given later in the file.
;;;
;;; 4) Add a help ("h") command to the editor. This could be as simple
;;; as listing the available commands.
;;;
;;; 5) Make the editor "extensible" via user-defined macros or editor
;;; commands written in Scheme.
;;;
;;; 6) Modify the editor to provide more descriptive error messages that
;;; diagnose the problem and attempt to give some help. For example,
;;; if the editor receives "(r 1)" it might respond with:
;;; "Two few arguments:
;;; Type (r pos exp) to replace the expression at position pos
;;; with the expression exp."
;;; This should be implemented in conjunction with the help command.
;;; Should it be possible to disable such verbose error messages?
;;; Implementation:
;;;
;;; The main editor loop and many of the help functions operate on a
;;; set of "registers". These registers are described below:
;;;
;;; s The current find object. s is initially #f, and is bound to a
;;; pair containing the find object when the first (f <obj>) command
;;; is seen. The identical f and (f) commands use the saved object.
;;;
;;; p The parent of the current expression. This is initially a list
;;; of one element, the argument to edit. It is updated by various
;;; movement commands.
;;;
;;; i The index of the current expression in the parent (p). This is
;;; initially 0. It is updated by various movement commands.
;;;
;;; b The "back" chain; actually a list containing the registers p, i
;;; and b for the parent of the current expression. It is initially
;;; (). It is updated by various movement commands.
;;;
;;; Bugs:
;;;
;;; When editing a circular structure, it is possible for the editor to
;;; get lost. That is, when the parent node of the current expression
;;; is changed by a command operating on a subexpression of the current
;;; expression, the index for the current expression may become incorrect.
;;; This can result in abnormal termination of the editor. It would be
;;; fairly simple to check for this (in list-ref) and reset the editor,
;;; and it may be possible to use a different set of registers to avoid
;;; the problem altogether.
(define edit #f) ; assigned within the let expression below
(let ()
(define cmdeq?
;; used to check command syntax
(lambda (cmd pat)
(and (pair? cmd)
(eq? (car cmd) (car pat))
(let okargs? ([cmd (cdr cmd)] [pat (cdr pat)])
(if (null? pat)
(null? cmd)
(and (not (null? cmd))
(okargs? (cdr cmd) (cdr pat))))))))
(define find
;; find expression within or to right of current expression
(lambda (s0 p0 i0 b0)
(define check
(lambda (p i b)
(if (equal? (list-ref p i) (car s0))
(wrlev s0 p i b)
(continue p i b))))
(define continue
(lambda (p i b)
(let ([e (list-ref p i)])
(if (atom? e)
(let next ([p p] [i i] [b b])
(let ([n (maxref p)])
(if (or (not n) (< i n))
(check p (+ i 1) b)
(if (null? b)
(search-failed s0 p0 i0 b0)
(apply next b)))))
(check e 0 (list p i b))))))
(continue p0 i0 b0)))
(define maxref
;; use "hare and tortoise" algorithm to check for circular lists.
;; return maximum reference index (zero-based) for a list x. return
;; -1 for atoms and #f for circular lists.
(lambda (x)
(let f ([hare x] [tortoise x] [n -1])
(cond
[(atom? hare) n]
[(atom? (cdr hare)) (+ n 1)]
[(eq? (cdr hare) tortoise) #f]
[else (f (cddr hare) (cdr tortoise) (+ n 2))]))))
(define move
;; move to subexpression specified by x and pass current state to k.
(lambda (x s p i b k)
(cond
[(eqv? x 0) (k s p i b)]
[(eq? x '*)
(let ([m (maxref (list-ref p i))])
(if m
(k s (list-ref p i) '* (list p i b))
(invalid-movement s p i b)))]
[(> x 0)
(let ([m (maxref (list-ref p i))] [x (- x 1)])
(if (or (not m) (>= m x))
(k s (list-ref p i) x (list p i b))
(invalid-movement s p i b)))]
[else
(let ([m (maxref (list-ref p i))] [x (- -1 x)])
(if (and m (>= m x))
(let ([x (- m x)])
(k s (list-ref p i) x (list p i b)))
(invalid-movement s p i b)))])))
(define proper-list?
;; return #t if x is a proper list.
(lambda (x)
(and (maxref x)
(or (null? x) (null? (cdr (last-pair x)))))))
(define list-ref
;; reference list ls element i. i may be *, in which case return
;; the last pair of ls.
(lambda (ls i)
(if (eq? i '*)
(cdr (last-pair ls))
(car (list-tail ls i)))))
(define list-set!
;; change element i of ls to x.
(lambda (ls i x)
(if (eq? i '*)
(set-cdr! (last-pair ls) x)
(set-car! (list-tail ls i) x))))
(define list-cut!
;; remove element i from ls.
(lambda (ls i)
(let ([a (cons '() ls)])
(set-cdr! (list-tail a i) (list-tail a (+ i 2)))
(cdr a))))
(define list-splice!
;; insert ls2 into ls1 in place of element i.
(lambda (ls1 i ls2)
(let ([a (list-tail ls1 i)])
(unless (null? (cdr a))
(set-cdr! (last-pair ls2) (cdr a)))
(set-car! a (car ls2))
(set-cdr! a (cdr ls2)))
ls1))
(define list-ap*!
;; place parens from element i through last pair of ls.
(lambda (ls i)
(let ([a (list-tail ls i)])
(let ([c (cons (car a) (cdr a))])
(set-car! a c)
(set-cdr! a '())))
ls))
(define list-ap!
;; place parens from element i0 through element i1.
(lambda (ls i0 i1)
(let ([a (list-tail ls i0)] [b (list-tail ls i1)])
(let ([c (cons (car a) (cdr a))])
(set-car! a c)
(if (eq? a b)
(set-cdr! c '())
(begin (set-cdr! a (cdr b))
(set-cdr! b '())))))
ls))
(define wrlev
;; write current expression to level 2, length 10 and continue.
(lambda (s p i b)
(parameterize ([print-level 2] [print-length 10])
(printf "~s~%" (list-ref p i)))
(edit-loop s p i b)))
(define wr
;; write current expression and continue.
(lambda (s p i b)
(printf "~s~%" (list-ref p i))
(edit-loop s p i b)))
(define pplev
;; pretty print current expression to level 2, length 10 and continue.
(lambda (s p i b)
(parameterize ([print-level 2] [print-length 10])
(pretty-print (list-ref p i)))
(edit-loop s p i b)))
(define pp
;; pretty print current expression and continue.
(lambda (s p i b)
(pretty-print (list-ref p i))
(edit-loop s p i b)))
(define not-a-proper-list
;; complain and continue.
(lambda (s p i b)
(printf "structure is not a proper list~%")
(edit-loop s p i b)))
(define cannot-dp-zero
;; complain and continue.
(lambda (s p i b)
(printf "cannot remove parens from current expression~%")
(edit-loop s p i b)))
(define pos2-before-pos1
;; complain and continue.
(lambda (s p i b)
(printf "second position before first~%")
(edit-loop s p i b)))
(define invalid-movement
;; complain and continue.
(lambda (s p i b)
(printf "no such position~%")
(edit-loop s p i b)))
(define unrecognized-command-syntax
;; complain and continue.
(lambda (s p i b)
(printf "unrecognized command syntax~%")
(edit-loop s p i b)))
(define search-failed
;; complain and continue.
(lambda (s p i b)
(printf "search failed~%")
(edit-loop s p i b)))
(define no-previous-find
;; complain and continue.
(lambda (s p i b)
(printf "no previous find command~%")
(edit-loop s p i b)))
(define edit-loop
;; read command and process.
(lambda (s p i b)
(let ([x (begin (printf "edit> ") (read))])
(cond
[(eof-object? x) (newline)] ; need newline after eof
[(eq? x 'q)] ; do not need newline after q
[(eq? x 'p) (wr s p i b)]
[(eq? x '?) (wrlev s p i b)]
[(eq? x 'pp) (pp s p i b)]
[(eq? x '??) (pplev s p i b)]
[(or (integer? x) (eqv? x '*)) (move x s p i b wrlev)]
[(eq? x 't)
(let f ([p p] [i i] [b b])
(if (null? b)
(wrlev s p i b)
(apply f b)))]
[(eq? x 'b)
(if (pair? b)
(apply wrlev s b)
(invalid-movement s p i b))]
[(eq? x 'n)
(let ([n (maxref p)])
(if (and (not (eq? i '*)) (or (not n) (< i n)))
(wrlev s p (+ i 1) b)
(invalid-movement s p i b)))]
[(eq? x 'pr)
(if (and (not (eq? i '*)) (> i 0))
(wrlev s p (- i 1) b)
(invalid-movement s p i b))]
[(or (eq? x 'f) (cmdeq? x '(f)))
(if s
(find s p i b)
(no-previous-find s p i b))]
[(cmdeq? x '(f x))
(find (cons (cadr x) '()) p i b)]
[(and (cmdeq? x '(r x x))
(or (integer? (cadr x)) (eq? (cadr x) '*)))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-set! p0 i0 (caddr x))))
(wrlev s p i b)]
[(cmdeq? x '(s x x))
(list-set! p i (subst! (caddr x) (cadr x) (list-ref p i)))
(wrlev s p i b)]
[(and (cmdeq? x '(d x)) (eqv? (cadr x) 0))
(list-set! p i '())
(wrlev s p i b)]
[(and (cmdeq? x '(d x)) (eq? (cadr x) '*))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(set-cdr! (last-pair p0) '())
(wrlev s p i b)))]
[(and (cmdeq? x '(d x)) (integer? (cadr x)))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-set! p i (list-cut! p0 i0))
(wrlev s p i b)))]
[(and (cmdeq? x '(dp x)) (eqv? (cadr x) 0))
(let ([e (list-ref p i)])
(if (and (pair? e) (null? (cdr e)))
(begin (list-set! p i (car e))
(wrlev s p i b))
(cannot-dp-zero s p i b)))]
[(and (cmdeq? x '(dp x))
(and (integer? (cadr x)) (not (= (cadr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(let ([e0 (list-ref p0 i0)])
(if (or (proper-list? e0)
(and (pair? e0) (eqv? i0 (maxref p0))))
(begin (if (null? e0)
(list-set! p i (list-cut! p0 i0))
(list-splice! p0 i0 e0))
(wrlev s p i b))
(not-a-proper-list s p i b)))))]
[(and (or (cmdeq? x '(ap x)) (cmdeq? x '(ap x x)))
(memv (cadr x) '(0 *)))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-set! p0 i0 (list (list-ref p0 i0)))
(wrlev s p i b)))]
[(and (cmdeq? x '(ap x x))
(and (integer? (cadr x)) (not (= (cadr x) 0)))
(eq? (caddr x) '*))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-ap*! p0 i0)
(wrlev s p i b)))]
[(and (cmdeq? x '(ap x x))
(and (integer? (cadr x)) (not (= (cadr x) 0)))
(and (integer? (caddr x)) (not (= (caddr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(move (caddr x) s p i b
(lambda (s1 p1 i1 b1)
(if (>= i1 i0)
(begin (list-ap! p0 i0 i1)
(wrlev s p i b))
(pos2-before-pos1 s p i b))))))]
[(and (cmdeq? x '(ib x x))
(and (integer? (cadr x)) (not (= (cadr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-splice! p0 i0 (list (caddr x) (list-ref p0 i0)))
(wrlev s p i b)))]
[(and (cmdeq? x '(ia x x))
(and (integer? (cadr x)) (not (= (cadr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-splice! p0 i0 (list (list-ref p0 i0) (caddr x)))
(wrlev s p i b)))]
[(and (cmdeq? x '(sb x x))
(and (integer? (cadr x)) (not (= (cadr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-splice! p0 i0
(append (caddr x) (list (list-ref p0 i0))))
(wrlev s p i b)))]
[(and (cmdeq? x '(sa x x))
(and (integer? (cadr x)) (not (= (cadr x) 0))))
(move (cadr x) s p i b
(lambda (s0 p0 i0 b0)
(list-splice! p0 i0 (cons (list-ref p0 i0) (caddr x)))
(wrlev s p i b)))]
[else
(unrecognized-command-syntax s p i b)]))))
(set! edit
;; set up keyboard interrupt handler and go.
(lambda (e)
(let ([p (cons e '())])
(let ([k (call/cc (lambda (k) k))]) ; return here on interrupt
(parameterize ([keyboard-interrupt-handler
(lambda ()
(printf "reset~%")
(k k))])
(wrlev #f p 0 '())
(car p)))))))