Last modified on Mon Oct 27 11:50:33 PST 1997 by heydon modified on Thu Jun 31 12:00:00 PDT 1997 by leifer This file documents bugs and/or inefficiencies in the compiler, assembler, and unparser. BUGS ========================================================================== o The expression "e1 # e2" is incorrectly evaluated as "NOT(e1 = e2)", contradicting the atomicity of "#" as listed in the spec. Example: "1/0 # 1/0" evaluates to TRUE, though it should evaluate to FALSE. o Unparsing ELSE "|" should use a united breakpoint. o When the command "IF x ~ y, y ~ x :: SKIP FI" is compiled, one of the nodes in the result AST is "x ~ y AND y ~ x". However, this node does not have a valid backpointer. o The compiler mistakenly complains about a cycle of near constraints because hints are not being pushed through CONS's (e.g. RightAngle.V4). Another example is that "R2.Length" breaks if "Math.Sqrt" provides a hint for "y" that is a function of "x". o Sometimes, extra blank lines are produced before and after lex errors. Done on Thu Jul 24 13:29:04 PDT 1997 by leifer and heydon o Changed JunoASTUtils.AlwaysDefined so that the negation of a literal number is considered to be always defined. This also required a change to the assembly of unary minus. Done on Thu Jul 24 13:29:04 PDT 1997 by leifer and heydon o Changed JunoASTUtils.NewPoint so that literal pairs with negated values get allocated with JunoAST.UMinus nodes. Done on Thu Jun 26 15:19:04 PDT 1997 by heydon o The compiler was not putting literals on the left-hand sides of equalities soon enough in its processing. As a result, hints were not being propagated through equalities as often as they could have been. In particular, the code that swapped the roles of left- and right-hand sides of an equality has been moved from "JunoCompileNF.Irreducible" to "JunoCompileNF.B1" (the specification for "JunoCompileNF.Normalize", which calls "B1", had already included this requirement, but the original implementation did not meet that specification). Done on Thu Jun 26 14:59:01 PDT 1997 by heydon o The nested procedure "JunoCompileNF.Phase2" was destructively setting the "frozen" bit of a "JunoAST.NearVarLink". This could cause the precondition of "JunoCompile.C2p" to fail on a subsequent compilation. The fix was to change "Phase2" so it set the "frozen" bit of a *copy* of the "NearVarLink" in question. Done on Mon Feb 24 17:19:57 PST 1997 by heydon o The fix from 28-Jan, 10:45 was still generating a UJUMP instruction on return from some functional procedure calls when it shouldn't have been. This was causing non-deterministic behavior, since the condition bit is no longer explicitly set at the end of the code for a user-defined procedure. The fix was to the "JunoAssemble.AfterCall" procedure to only generate the UJUMP instruction on return from a call to a user-defined function, but not on return from an external functional procedure or a user-defined functional procedure. Done on Tue Jan 28 13:45:02 PST 1997 by heydon o Fixed bugs in JunoCompileNF in which parenthesized expressions were not handled correctly. This also involved a change to the "JunoASTUtils.MapArgs" procedure. For example, the command "VAR x = (2) IN x := 3 END" was causing Juno to crash. Done on Tue Jan 28 10:45:02 PST 1997 by heydon o A recent change to the Juno machine in which failed calls to external procedures are always reported as run-time errors necessitated changes to the assembler. In particular, the code generated by the assembler could be simplified because: 1) no code is required to check the condition bit after a call to an external procedure (this is now done by the CALLEXT and APPLY byte codes), 2) calls to external procedures are always defined, and 3) the prologue to the assembly of a user-defined procedure no longer needs to include a C_ON instruction to set the condition bit, since the condition bit is no longer checked by code following an APPLY instruction (and the implementation of the APPLY instruction only checks the bit after calling an external procedure). Done on Mon Jan 27 19:10:13 PST 1997 by heydon o Ramon Felciano reported a crash in which the Juno machine was encountering an unknown byte code. The problem turned out to be that the assembler was generating bad code. In particular, it was adding a reference to the bad label "JunoAssemble.NoLabel". I therefore added an assertion to "JunoAssemble.AddReference" that the label being referred to was in fact valid. The root cause of the problem, however, was that "JunoChkBNF.TotalCmd" was not strict enough: in order for a projection command to be total, any hints (or known values) supplied for the projected variables must be defined everywhere; the code was not checking for this. Done on Mon Jan 27 19:10:13 PST 1997 by heydon o The code to check if a command is total declares "VAR..IN..END" statments total so long as their body is total. This is actually incorrect, if some of the introduced variables have equality constraints on them. The equality constraints might be impossible to satisfy, in which case the "VAR" statement will fail. This bug was fixed as part of the previous change. Done on Wed May 8 19:14:30 PDT 1996 by heydon o Lyle Ramshaw reported that Juno was overflowing its stack compiling a large command. The main culprit turned out to be that JunoCompile.AnnotateAtoms handled sequences recursively. I changed it to have an iterative implementation. Done on Tue Jan 2 17:27:49 PST 1996 by heydon o The compiler should check that calls to CLOSE and APPLY have at least one argument. Otherwise, the assembler crashes. Done on Thu Sep 28 13:18:56 PDT 1995 by heydon o The change of 21-July-1995 in which the "Expr" procedure was made iterative had a serious bug that was causing some labels never to be assigned locations. This led to crashes at run-time. Done on Sun Jul 2 14:49:25 PDT 1995 by heydon o The compiler was not adding a backpointer for the "M.Save()" and "M.Restore()" nodes created from a "SAVE M IN ... END" node [heydon]. Hence, if "M" named an interface that was not imported in a module, the compiler would crash trying to trace the backpointers to highlight the error. I also changed the type of a "JunoAST.Save" node so the interface name was a "JunoAST.QId"; this makes it possible to highlight the interface name in the event of an error. Done on Wed Jun 28 00:14:59 PDT 1995 by heydon o Assignment statements in which the cardinalities of the left- and right-hand sides differed were being compiled without complaint [rustan]. I changed "JunoCompile.AnnotateAtoms" to report an error if necessary. Done on Sun Jan 29 23:36:31 PST 1995 by heydon o There were bugs in the specifications of the procedures "JunoCompile.Cmd.C2p", "JunoCompile.Cmd.C2pp", and "JunoCompileNF.ToCmd", as well as a bug in the way rule C2.24 was implemented in the procedure "JunoCompile.Cmd.C2p". The bug was causing certain queries to be compiled without initializing some of the hinted variables [ramshaw]. In particular, commands of the form "VAR x ~ hint IN C -> { A | B }" did not compile correctly. Done on Fri Jan 20 15:42:17 PST 1995 by heydon o If the current command consists of a single projection that contains more than one occurrence of the same variable, Juno crashes while dragging [ramshaw]. We decided that multiple occurrences of a variable in a projection or existential quantification should be a static error. I fixed "JunoCompile.AnnotateAtoms" to check for this condition, and to raise an exception. I also changed the relevent sections of the language definition. Done on Tue Oct 18 11:08:03 PDT 1994 by heydon o The assembler is not laying down code after the call to a compiled FUNC to check that the function was not undefined. Done on Fri Aug 5 12:38:00 PDT 1994 by heydon o Juno crashes when compiling declaractions such as "CONST Hide = FALSE;" [ramshaw]. The bug is that the code for compiling an expression is calling ChkBNF *after* AnnotateAtoms. Done on Mon Jun 20 15:02:24 PDT 1994 by heydon o Sometimes, compiling a command causes a stack overflow [ramshaw]. We should change the compilation procedures to fork a larger stack to avoid this problem. Done on Fri Jun 10 11:30:21 PDT 1994 by heydon o Need to implement JunoAssemble.PushUShort and JunoAssemble.PushULong correctly. Done on Sun May 1 17:33:51 PDT 1994 by heydon o There seems to be a bug in "JunoCompileNF.ToCmd". An incorrect assignment is being extracted when the "Area" function in the file "juno-src/debug/- JunoCompileNF-Bug.juno" is compiled. The bug was in "JunoCompileNF.Irreducible". This procedure was flipping the two sides of an equality to guarantee that an atom was on the left side, but it did not copy the "b3cnt" field to the newly created formula. Done on Mon Sep 13 12:37:33 PDT 1993 by heydon o Fix comment unparsing: "\n\n" for a new paragraph and "|" for verbatim text. Done on Wed Sep 1 11:30:14 PDT 1993 by gnelson o Fix the unparser. Done on Fri Aug 20 21:32:00 PDT 1993 by heydon o "JunoASTUtils.RemFrozen" sets the "frozen" bit of all the variables in the result, even if the variables were unhinted. The result is that the code compiled for real-time dragging falsely asserts that some variables have initial values. Done on Sun Aug 15 20:53:21 PDT 1993 by heydon o The compiler erroneously complains that certain constructs are not allowed in a constraint, even when they haven't been included directly. For example, in the command "IF x :: x = 2 -> IF NOT x = 3 -> y :: y = x -> SKIP FI FI", the compiler complains that "NOT" is not allowed in a constraint, even though the variable "x" is known at the point of the "NOT". The complaint arises because an early stage of the compiler rewrites "P -> x :: S" as "x :: P -> S", thereby incorporating the test "NOT x = 3" into the constraint used to solve for "y". The fix is to change the JunoCompileNF and JunoCompile modules to treat NOT and OR specially. There are three things to change: 1. Change the Normalize procedure to handle NOT and OR. The array produced by Normalize may contain NOT and OR nodes. The argument(s) to these nodes should be normalized recursively. OR nodes with a "TRUE" argument become "TRUE", and are ignored. 2. Add a Phase0 processing step to pull NOT and OR nodes out of the argument constraint as queries. Raise an exception saying that NOT and OR are not allowed in constraints if any contains an unknown. 3. Augment the NOT and OR compilation rules to call JunoCompileNF.ToCmd on any normalized argument(s). [Actually, the fix did not require step 2; it came for free.] Done on Sat Aug 14 18:18:47 PDT 1993 by heydon o Occassionally, grouped expressions are not being ignored in constraints. For example, the compiler complains about the parenthesized expression "(cy - dy)" in the following definition: PRED EqVer(a, b, c, d) IS (E ax, ay, bx, by, cx, cy, dx, dy :: a = (ax, ay) AND b = (bx, by) AND c = (cx, cy) AND d = (dx, dy) AND ay - by = (cy - dy)) END; Done on Wed Jul 7 23:32:56 PDT 1993 by heydon o On a parse error, the "JunoParse.Error" argument's "additional" field is missing the first space after the problem token. The fix: Contrary to the specification, the implementation of JunoLex.Close was testing if the current character was a space; if so, it was returning the empty string. It is now the clients job to skip white space if they wish. Done on Wed Jun 30 12:48:30 PDT 1993 by heydon o Assembler is not generating code to test condition bit on return from external procedures. Done on Tue Jun 29 10:04:03 PDT 1993 by heydon o Parser is parsing operators with equal precedence right-associatively instead of left-associatively. To fix this bug, I added new non-terminals Expr1Tail and Expr2Tail to the grammar, and made the "ast" parameter of the corresponding procedures in JunoParse.m3 VAR (*INOUT*) parameters instead of VAR (*OUT*) parameters. Done on Tue May 25 10:53:24 PDT 1993 by heydon o Compiler crashes if a constraint contains a procedure call that can't be eliminated during the known-elimination phase. The bug was caused because the JunoCompile.GetFunc() procedure treated every JunoAST.Call node as a function call. The code now distinguishes between function calls and procedure calls by checking the "normal_form" annotation of the JunoAST.Call node: the JunoCompile.AnnotateAtoms() procedure sets this field to a non-NIL value in the case of a function call, but leaves it with its initial (NIL) value in the case of a procedure call. If the JunoAST.Call node is a procedure call, JunoCompile.GetFunc raises "Error". Done on Tue May 25 10:49:45 PDT 1993 by heydon o Compiler erroneously reports an error for the procedure definition "PROC res := P(x) IS res := F(x) END;" when "F" is a function. The bug was caused by the fact that the parser was parsing the body as a procedure call, rather than as an assignment. I changed the parser so that it promotes an assignment to a procedure call *only* when it is guaranteed to be a procedure call (in the absence of semantic information); namely, when there are at least two variables on the left side of the assignment, and exactly one JunoAST.Call expression on the right side of the assignment. An expression of the form "x := P(y)", where P is a procedure, will be parsed as an assignment, but that is okay, since P is a functional procedure. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Avoid the problem of "ConsCell.Size": inlining should not require qualification of Id's. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Avoid stack overflow. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Sort REL hints. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o (E x ~= e :: P) == (E x :: x ~= e AND P). Done on Mon Feb 1 16:31:14 PST 1993 by heydon o The assembler does not currently generate code to reset the run-time stack to its original configuration when evaluating an expression if that expression is undefined. Done on Fri Jan 29 22:09:35 PST 1993 by heydon o The Juno language has explicit provisions for the case where a function is undefined. Currently, the built-in functions take an offset argument that indicates a location to branch to in the event that the built-in is undefined. To handle user-defined function calls, the assembler must compile the command associated with a function body such that run-time errors reset the machine's condition bit, while successful function evaluations *set* that bit. The assembler must then generate code after a function *call* to branch to the undefined label iff the condition bit is not set. Done on Fri Jan 29 15:56:40 PST 1993 by heydon: o If an actual argument to a user-defined predicate is undefined, then the predicate call should evaluate to FALSE. If an actual argument to a user-defined function is undefined, then the function call should evaluate to UNDEFINED. TO DO ========================================================================= o Allow closing over FUNCS as well as procedures. o Allow INOUT closure values. Done on Sun Oct 26 11:48:02 PST 1997 by heydon o Exposed procedure "JunoASTUtils.NewNumber" in "JunoASTUtils.i3". Done on Mon Jan 27 19:14:14 PST 1997 by heydon o Encapsulated "JunoAssemble.closeSlot" and "JunoAssemble.applySlot" global variables in a new "BuiltInSlots" module. Moved the "AlwaysDefined" procedure from "JunoAssemble" to "JunoASTUtils" for more general use. Done on Fri Mar 29 14:07:29 PST 1996 by heydon o Changed interfaces to procedures in "JunoUnparse" to take an explicit precision to which real numbers are unparsed. Done on Fri Sep 9 09:13:49 PDT 1994 by heydon o Change lexer to allow identifiers to begin with "_". Done on Fri Jun 10 11:29:50 PDT 1994 by heydon o Change the compiler/assembler so they don't use the global code table for storing Juno NIL and Juno numbers that appear in parse trees. Hence, "JunoAST.Nil" and "JunoAST.Number" don't need an "index" field; this is only needed for "JunoAST.Text" values. Use the new "PUSHNIL" and "PUSHNUM" instructions to get Juno Nil and Juno numbers on the stack instead of "PUSHG". Also, change the "val" field of a "JunoAST.Number" so it is a "JunoValue.Real" instead of a "REF JunoValue.Real". Done on Fri Jun 10 11:29:42 PDT 1994 by heydon o Change the type "JunoAST.Number" to store a REAL instead of a REF REAL. Done on Wed Jun 1 10:05:07 PDT 1994 by heydon o Add support for compiling closures. This includes QId's that name procedures, as well as the special procedures CLOSE and APPLY. Done on Wed May 18 19:12:22 PDT 1994 by heydon o Change JunoAST.QId so that an unqualified identifier has the name in the "id1" field, and "id0" is "JunoAST.NilId". Done on Wed Mar 23 09:43:18 PST 1994 by heydon o Change the Juno lexer to use the new IP "Lex" interface to read reals. Done on Wed Mar 23 09:42:50 PST 1994 by heydon o Improve lexing efficiency. The current lexer appends each character to a TEXT when it reads text strings and comments. [heydon] Done on Fri Jan 7 17:57:18 PST 1994 by heydon o Get rid of selective imports from parser and JunoAST. Done on Wed Sep 1 09:53:01 PDT 1993 by heydon o Move "JunoASTUtils.RemFrozen" and "JunoASTUtils.SkipNamed" to "Drag.i3"? Done on Thu Aug 19 17:39:49 PDT 1993 by heydon o ATAN(x) => ATAN(y, x). This will require changes to the machine and solver as well as to the compiler. Done on Mon Aug 16 22:48:47 PDT 1993 by heydon o LIM-like syntax for projection Done on Sun Aug 15 20:53:21 PDT 1993 by heydon o Add support for "TRUE OR ..." at the start of a constraint. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Check errors at annotation time. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Add compilation/assembler support for constants and global variables. Done on Tue Mar 30 11:30:35 PST 1993 by heydon (actually done a while ago) o Get rid of INTERFACE/MODULE distinction, and instead add PRIVATE designator to declarations. Add ability to parse private comments too. INEFFICIENCIES ================================================================ o The code for unparsing comments could be made more efficient by explicitly calculating the place to break each line, rather than inserting breaks between every word. We should also fix the code to break at hyphens. o The various passes of B3 that implement topological sort are not doing so very efficiently. They should keep a queue of predicates to process; as a predicate is processed, new predicates may need to be added to the queue. o The procedure JunoCompile.AnnotateAtoms uses StackTbl.T's to maintain scope information, when we could use Scope.T's and global variables instead. o A peephole optimizer could eliminate simple redundancies in assembled code. See ~heydon/juno/notes/optimizations.txt for examples. Done on Fri Jul 21 11:02:04 PDT 1995 by heydon o Changed the recursive version of "JunoAssemble.Cmd.ExprListTail" to use iteration when generating code to push a list of expressions onto the stack. This was to save stack frames to avoid overflowing the thread stack when compiling list expressions with lots of elements. I also cleaned up the interface to this procedure, simplified the "ExprList" procedure, and removed the "ExprListMid" procedure. Done on Thu May 11 15:50:22 PDT 1995 by heydon o Changed recursive versions of "JunoCompile.Cmd.C1", "JunoCompile.Cmd.C2", and "JunoAssemble.Cmd.Cmd0" to use iteration when compiling/assembling semi-colon-separated sequences of commands. This was to save stack frames to avoid overflowing the thread stack. Done on Wed Apr 26 17:58:42 PDT 1995 by heydon o Changed the implementation of "JunoCompile.C1Grd" to invoke "C1Grd" directly (rather than "C1") when possible. This saves a procedure call (and hence, a precious stack frame). Also, I made the thread stack size for compilation threads 5 times the default, rather than 3 times the default. We really need to treat certain cases iteratively, rather than recursively, such as processing long sequences of commands. But such iterative code would have to be added in several places. Done on Mon Jun 20 13:43:22 PDT 1994 by heydon o The nested procedure "JunoCompile.Cmd.C1" has a large stack frame. The sub-case of this procedure in which the "cmd" is a guard can be separated into a separate procedure so that the stack frames are smaller in the other cases. Done on Tue Mar 30 11:21:46 PST 1993 by heydon (actually done in late Feb) o Each time we substitute a new predicate or function body in B4, we are unflattenning and reflattening the current query! Done on Tue Feb 9 17:00:19 PST 1993 by heydon o The program structure would be simpler if JunoCompile.AnnotateAtoms caught as many compile-time errors as possible. Many static checks are currently performed in the compiler and assembler, when they could be performed in the initial annotation phase. Done on Tue Feb 9 17:00:19 PST 1993 by heydon o The annotation phase of the compiler identifies the type of each qualified identifier. However, we are not caching enough information with each QID to prevent future Scope.Lookups. It would probably be faster (and easier to program) to use a little extra space to store the necessary scope information to prevent calls to Scope.Lookup during future phases of the compiler and assembler. To do this, we need to break the annotation procedure into three parts -- commands, expressions, and predicates -- in order to distinguish between uses of JunoAST.Call, etc.