[Cyan]<CedarChest6.1>Documentation>MispDoc.Tioga!1

MispDoc.tioga

Spreitzer, July 30, 1985 2:32:02 pm PDT

Pavel, June 20, 1985 1:40:12 pm PDT

MISP

CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY

Misp

Mike Spreitzer

Abstract: Misp (My LISP) is a LISP-like interpreter.

Created by: Mike Spreitzer

Maintained by: Mike Spreitzer <Spreitzer.pa>

Keywords: Misp, LISP, Interpreter, Interactive, Evaluate

XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304

For Internal Xerox Use Only

1. General

Misp evaluates LIST OF REF ANY's in a LISP-like fashion. Notable differences are the static scope rules, and the eagerness to include random Cedar values. Misp is much inspired by Brian Smith's 2-LISP.

2. Data Types

Misp is willing to pass around anything that can be stored in a REF ANY (hence its usefulness in the Cedar enviroment). Furthermore, for some particular kinds of REF it can do even more:

LIST OF REF ANY:

There is a literal notation for input of lists: ( elt elt ... elt ).

There are a number of list manipulation primitives; see below.

The equal operator compares lists element by element.

ATOM:

There is a literal notation for input of atoms: pName.

ROPE:

There is a literal notation for input of ROPEs: "contents".

The equal operator compares ROPEs by contents.

There are some operators for manipulating ROPEs; see below.

REF INT, REF REAL:

There is a literal notation for input of numbers: n.

The equal operator compares numbers by value, not address.

There are a number of arithmetic primitives; see below.

REF Complex.VEC:

The equal operator compares complex numbers by value too.

Many of the arithmetic primitives work for complex numbers.

REF (Misp.TimeRec = RECORD [t: BasicTime.GMT])

The equal operator compares times by value too.

There are some operators for manipulating times; see below.

REF BOOL:

BEWARE! Misp uses the standard LISPy encoding of Boolean values (NIL for FALSE, anything else considered TRUE). Any non-NIL REF BOOL will thus be treated as TRUE. Booleans are used in several standard Boolean functions as well as flow-control constructs.

3. Evaluation

The rules for evaluating a REF ANY are:

1) if it is an ATOM, return the binding of that atom in the current environment.

2) if it is a LIST OF REF ANY:

2a) Evaluate the first element of the list; it must evaluate to a closure.

2b) If the closure wants its arguments evaluated, evaluate the rest of the list.

2c) Invoke the closure on the list of arguments.

3) in any other case, the value is the REF ANY itself.

4. Binding

Whenever there is an occasion to bind a value against a pattern (e.g., in lambda expressions, lets, and dos), a slightly more general-than-usual mechanism is used. The rules are:

1) When the pattern is an atom, bind it to the value

2) When the pattern is a list, the value must also be a list. Recursively bind elements of the pattern list to corresponding elements of the value list. If the value list is too small, it is extended with NILs. The pattern list must be at least as long as the value list.

Rule (2) gives ordinary lambda expressions the power to take an unspecified number of arguments. As an example, the following code extends a binary operation binop, with identity element id, into a function on lists in the obvious way:

(defun extend (binop id)

(lambda args -- args will be bound to the entire list of arguments

(do

((ans id (binop ans (car l)))

(l args (cdr l)))

((not (null l)) ans)

nil

)

5. NLambdas

An nlambda expression is one that does not evaluate its arguments. Also, it gets access to the environment it was called in. For example, one could define something like setq, except that it takes its arguments in reverse order:

(ndefun setqr ((val name) env)

(set name (eval val env) env)

)

6. Catch and Throw

Misp programs have a simple ability to signal and catch exceptional conditions. In the simplest case, the function (abort) raises the Cedar ABORTED signal. The Misp form (catchAborted x y) evaluates x, returning the value of y if ABORTED is raised meanwhile.

For more demanding applications, Misp provides the ability to raise and catch an unlimited variety of signals. The expression (throw id v) raises a condition with the atom id and the value v. Such conditions can be handled with the form (catch id x fn) which evaluates x and, if a condition with atom id and value v is raised, returns the result of applying fn to v. If no fn is given, the identity function is used instead.

For example, here is a hacky way of implementing the lookup operation on association lists, where the alist is represented as a list of lists of length 2, (key value). If the key is not bound in the alist, this function raises the NotFound signal:

(defun lookup (key alist)

(catchq Found

(do

( (list alist (cdr list)) )

( (not (null list))

(throwq NotFound key) )

(if (eq key (caar list))

(throwq Found (car list))

)

(lambda (assoc) (cadr assoc)))

)

7. Connection with the Cedar interpreters

Misp expressions can invoke both Cedar interpreters (the expression interpreter, and the statement interpreter) --- see cedarExpr and cedarStmt below. Misp adds to the Cedar expression interpreter a way to evaluate Misp expressions --- see &misp[...] below. The interesting thing about this is that the name spaces are properly inherited. The conversions are as follows:

Cedar To Misp:

In a Misp expression invoked from Cedar (via &misp[...]), a Cedar value that is some kind of REF appears unchanged. A Cedar value that is not a REF appears in Misp as REF to that Cedar value.

Misp To Cedar:

Since every Misp value is some kind of REF, this is easy --- a Misp value appears in Cedar as a REF ANY.

Here are some example uses of these features:

Using Cedar from Misp:

Misp> (defun cat (r1 r2 r3 r4 r5) (cedarExpr "Rope.Cat[r1, r2, r3, r4, r5]"))
<cat>
Misp> (cat "x" "y")
"xy"
Misp> (defun fmtType (x) (cedarStmt "{
s: IO.STREAM ← IO.ROS[];
IO.PutRope[s, \"REF \"];
PrintTV.PrintType[SafeStorage.GetReferentType[x], s];
&yield[IO.RopeFromROS[s]]
}"
))
<fmtType>
Misp> (fmtType 3)
"REF INT"
Misp> (fmtType "x yz")
"REF Rope.RopeRep"

Using Misp from Cedar:

% ← &misp["(sgn (complex 1 1))"]
^[x: 0.7071068, y: 0.7071068]

8. Predefined values

Control structures:

(prog x1 x2 ... xn) . . . => xn

(let ((p1 x1) ... (pn xn)) body) => body with p1 ← x1, ... pn ← xn

(do ((p1 initial1 next1) ... (pn initialn nextn)) (continuep [loopval]) body) =>
loopval (if present) or last body (if no loopval)

(if c xTrue [xFalse ← nil]) . => if c then xTrue else xFalse

(cond ((c1 [x1]) ... (cn [xn]))) . => if c1 then (x1, if present, else c1) else ... if cn then (xn, if present, else cn) else nil

(pause seconds: Real). . . => seconds

(abort) . . . . . . . => raise ABORTED

(catchAborted x y) . . . => x ! ABORTED => y

(catch id x [fn]) . . . . => x, or (fn v) if a (throw id v) occurs in evaluating x

(catchq id x [fn]) . . . => like catch, but id is not evaluated

(throw id v) . . . . . => signals id with value v (see section 6, above)

(throwq id v) . . . . => like throw, but id is not evaluated

Evaluation:

(eval form [env]) . . . => eval of form in environment

(apply fn args) . . . . => (fn . args)

(load "filename") . . . => $T
(Adds ".misp" onto filename unless an extension is explicitly given)

(cedarExpr "expr") . . . => Cedar Interpreter's evaluation of expr

(cedarStmt "stmt") . . . => Statment Interpreter's evaluation of stmt, which will normally be NIL, since Cedar statements don't have values; however the Cedar expression &yield[val] will instead abort further evaluation of the Cedar statement, and return the indicated value.

Input/output:

(print x1 x2 ... xn) . . . => prints values on output stream, not quoting ROPEs

(println x1 x2 ... xn) . . . => like print, but adds a newline on the end

(printval x1 x2 ... xn) . . => like print, but quotes ROPEs

(read) . . . . . . . => value from input stream

Constants:

NIL = NIL

nil = NIL

false = NIL

T = $T

t = $T

true = $T

Data constructors/accessors:

(quote x) . . . . . . => x, unevaluated

(list x1 x2 ... xn) . . . . => (x1 x2 ... xn)

(lambda args body) . . . => function value

(nlambda (args env) body) . => function value which doesn't evaluate its arguments

(unlambda fn) . . . . => (name pattern body env isN)

(cons x1 x2 ... xn). . . . => (x1 . (x2 . ... (xn-1 . xn)...))

NOTE that xn must be a list, due to Misp's use of Cedar LISTs

(car x) . . . . . . . => x.first

(cdr x) . . . . . . . => x.rest

(caar x) . . . . . . . => x.first.first

... and so on, up to cddddr

(nth n l) . . . . . . => l (.rest)^n .first

(rplaca l x) . . . . . => l, with l.first = x

(rplacd l x) . . . . . => l, with l.rest = x

(complex a b: Real). . . . => a+bi

(re c: Complex). . . . . => Re[c]

(im c: Complex). . . . . => Im[c]

(reim c: Complex). . . . => (Re[c] Im[c])

General predicates:

(eq x1 x2) . . . . . . => pointer compare

(equal x1 x2) . . . . . => value compare

(ne x1 x2) . . . . . . => value compare

(atom x) . . . . . . => type test, $T iff x is an ATOM

(envp x) . . . . . . => type test, $T iff x is an environment

(funcp x) . . . . . . => type test, $T iff x is a function

(listp x) . . . . . . => type test, $T iff x is a LIST OF REF ANY

(numberp x) . . . . . => type test, $T iff x is a REF INT, REAL, or COMPLEX

(ropep x) . . . . . . => type test, $T iff x is a ROPE

(stringp x) . . . . . => synonym for ropep

Environment manipulation:

(set name x [env]) . . . => x, binding name to x in env (evaluates name first)

(setq name x [env]) . . . => x, binding name to x in env

(defun name args body [env]) => bind name to (lambda args body) in env

(ndefun name (args env) body [env]) => bind name to (nlambda (args env) body) in env

(boundp name [env]) . . => is name bound in environment? (evaluates name first)

(emptyEnv [name [parent]]) => a new empty environment, nested under parent

List manipulation:

(append l1 l2 ... ln) . . . => Append[l1, l2, ... ln]

(mapcar fn al1 al2 ... aln) . => generalized inner product

(length l) . . . . . . => Length[l]

Boolean operations:

(and x1 x2 ... xn) . . . . => x1 & x2 & ... xn

(not x) . . . . . . . => ~x

(or x1 x2 ... xn) . . . . => x1 | x2 | ... xn

NOTE that (and) and (or) are lazy: they only evaluate as many arguments as necessary to guarantee the final result. Thus, (and) stops when it finds an argument which evals to NIL and (or) stops on the first non-NIL.

Numeric operations:

(round r: Real). . . . . => RoundLI[r]

(floor r: Real). . . . . => Floor[r]

(ceiling r: Real). . . . . => Ceiling[r]

(abs c: Complex). . . . => |c|

(sgn c: Complex). . . . => c/|c| or 0

(arg c: Complex). . . . => Im[Ln[c]] or 0

(exp c: Complex). . . . => Exp[c]

(ln c: Complex). . . . . => Ln[c]

(sin radians: Real). . . . => Sin[radians]

(cos radians: Real). . . . => Cos[radians]

(tan radians: Real). . . . => Tan[radians]

(plus c1 c2 ... cn: Complex). => c1 + c2 + ... cn

(minus c1 c2 ... cn: Complex). => c1 - c2 - ... cn

(mult c1 c2 ... cn: Complex). => c1 * c2 * ... cn

(div c1 c2 ... cn: Complex). . => c1 / c2 / ... cn

(quot c1 c2 ... cn: Complex). => Floor[...Floor[c1 / c2] / ... cn]

(rem c1 c2 ... cn: Complex). => (..(c1 rem c2) rem ... cn)

(min c1 c2 ... cn: Complex). => Min[c1, c2, ... cn]

(max c1 c2 ... cn: Complex). => Max[c1, c2, ... cn]

(lt r1 r2 ... rn: Real). . . => r1<r2 and ... rn-1<rn

(le r1 r2 ... rn: Real). . . => r1<=r2 and ... rn-1<=rn

(gt r1 r2 ... rn: Real). . . => r1>r2 and ... rn-1>rn

(ge r1 r2 ... rn: Real). . . => r1>=r2 and ... rn-1>=rn

(gcd i1 i2 ... in: Int). . . => Gcd[...Gcd[i1, i2], ... in]

(lcm i1 i2 ... in: Int). . . => Lcm[...Lcm[i1, i2], ... in]

Rope (string) operations:

(cat r1 r2 ... rn: ROPE). . . => Rope.Concat[...Rope.Concat[r1, r2], ... rn]

(consFinder opt1 ... optn: ATOM pattern: ROPE) => a TextFind.Finder

This compiles a text query into a form ready for quick searching. Possible options are:

$literal treat the pattern as a literal; this is default.

$pattern interpret metacharacters in the pattern (as in the Edit Tool).

$word the matched text must not have surrounding alphabetic characters.

$addBounds the pattern must match the entire subject (header field or message body).

$anywhere means neither $word nor $addBounds; this is the default.

$ignoreCase ignore case.

$testCase don't ignore case; this is the default.

(consFinderq opt1 ... optn: ATOM pattern: ROPE) => a TextFind.Finder

Like consFinder, but does not evaluate its arguments first.

(ropeMatch x subject: ROPE). => m: Matching

Matches x against the entire subject. x can be either a ROPE or a TextFind.Finder. Iff match fails, m = NIL.

(ropeFind x subject: ROPE). => m: Matching

Searches for x in the subject. x can be either a ROPE or a TextFind.Finder. Iff search fails, m = NIL. ropeMatch and ropeFind are the same when x is a Finder.

(ropeSubstitute m: Matching pattern: ROPE) => ROPE

Parses pattern like the EditTool's Replacement field, filling in named subfields from the Matching.

Time operations:

(timeDiff t1:Time t2:Time) => Number

t2 - t1, in seconds

(timeUpdate t:Time Dt:Number) => Time

t + Dt

(timeNow) => current Time

(timeFmt t:Time) => ROPE

(timeParse ROPE) => Time

See also the contents of MispStandards.misp, a file of Misp expressions that is (load)ed into every top-level environment.

Additions to the Cedar expression interpreter:

&misp[expr] . . . . . => Misp's evaluation of expr.

If expr is a ROPE or REF TEXT, it is first parsed by IO.GetRefAny, otherwise it's taken as is.

&yield[val] . . . . . => Makes val the value of the nearest dynamically enclosing (cedarStmt ...) evaluation.