USING: errors gadgets-tracks generic hashtables help io kernel
math memory sequences words compiler parser modules definitions
-tools alien ;
+tools alien inference ;
ARTICLE: "changes" "Changes in the latest release"
{ $heading "Factor 0.86" }
{ "Windows now update while being resized on Windows" }
}
}
+{ $subtopic "Stack effect inference"
+ { $list
+ { "The new " { $link infer. } " word should be called instead of " { $link infer } ", since it presents information in a more pleasing way" }
+ "Stack effect inference now infers variables read and written by a quotation to facilitate code comprehension and debugging"
+ }
+}
{ $subtopic "Module system"
{ $list
{ "The syntax for " { $link POSTPONE: PROVIDE: } " has changed, consult the documentation" }
- { "Modules can now provide documentation, see " { $link run-module } " and " { $link POSTPONE: MAIN: } }
- { "Modules can now provide a main entry point, see " { $link "documenting-modules" } }
+ { "Modules can now provide a main entry point, see " { $link run-module } " and " { $link POSTPONE: MAIN: } }
+ { "Modules can now provide documentation, see " { $link "documenting-modules" } }
}
}
{ $subtopic "Contributed libraries"
}
}
{ $subtopic "Contributed libraries"
- { $subtopic { "External process interface - " { $snippet "contrib/processes.factor" } }
+ { $subtopic "contrib/processes.factor"
{ $list "This is a new library" }
}
- { $subtopic { "Partial continuations - " { $snippet "contrib/partial-continuations.factor" } }
+ { $subtopic "contrib/partial-continuations.factor"
{ $list "This is a new library (Chris Double)" }
}
- { $subtopic { "HTTP server - " { $snippet "contrib/httpd/" } }
+ { $subtopic "contrib/httpd/"
{ $list
"File responder fixes"
"Inspector responder fixes"
{ "Add templating engine in " { $snippet "embedded.factor" } " (Alex Chapman)" }
}
}
- { $subtopic { "XML parser - " { $snippet "contrib/xml.factor" } }
+ { $subtopic "contrib/xml.factor"
{ $list
"Various updates for recent Factor changes"
"Improved XML output capabilities"
}
}
- { $subtopic { "Factory window manager - " { $snippet "contrib/factory/" } }
+ { $subtopic "contrib/factory/"
{ $list "Many updates" }
}
- { $subtopic { "Cryptography library - " { $snippet "contrib/crypto/" } }
+ { $subtopic "contrib/crypto/"
{ $list
"Added Base64 encoding (Doug Coleman)"
"Added Blum Blum Shub random number generator (Doug Coleman)"
"Added CRC32 checksum (Doug Coleman)"
}
}
- { $subtopic { "Space invaders/Intel 8080 emulator - " { $snippet "contrib/space-invaders/" } }
+ { $subtopic "contrib/space-invaders/"
{ $list
"Updated to use Factor UI instead of SDL (Chris Double)"
}
{ $subsection d-in }
{ $subsection meta-d }
"When a literal is encountered, it is simply pushed on the shadow stack. For example, the stack effect of the following quotation is inferred by pushing all three literals on the shadow stack, then taking the value of " { $link d-in } " and the length of " { $link meta-d } ":"
-{ $example "[ 1 2 3 ] infer ." "{ 0 3 }" }
+{ $example "[ 1 2 3 ] infer." "* Stack effect:" "( -- object object object )" }
"In the following example, the call to " { $link + } " expects two values on the shadow stack, but only one value is present, the literal which was pushed previously. This increments the " { $link d-in } " counter by one:"
-{ $example "[ 2 + ] infer ." "{ 1 1 }" }
+{ $example "[ 2 + ] infer." "* Stack effect:" "( object -- object )" }
"After the call to " { $link + } ", the shadow stack contains a \"computed value placeholder\", since the inferencer has no way to know what the resulting value actually is (in fact it is arbitrary)." ;
ARTICLE: "inference-combinators" "Combinator stack effects"
"Without further information, one cannot say what the stack effect of " { $link call } " is; it depends on the given quotation. If the inferencer encounters a " { $link call } " when the top of the stack is a computed value placeholder, a " { $link literal-expected } " error is raised."
-{ $example "[ [ + ] append call ] infer ." "... an error ..." }
+{ $example "[ [ + ] append call ] infer." "... an error ..." }
"On the other hand, applying " { $link call } " to a literal value behaves as if the quotation was substituted at that point:"
-{ $example "[ [ 2 + ] call ] infer ." "{ 1 1 }" }
+{ $example "[ [ 2 + ] call ] infer." "* Stack effect:" "( object -- object )" }
"Consider a combinator such as " { $link keep } ". The combinator itself does not have a stack effect. However, since the combinator is declared " { $link POSTPONE: inline } ", a given usage of it can have a stack effect:"
-{ $example "[ [ 2 + ] keep ] infer ." "{ 1 2 }" }
+{ $example "[ [ 2 + ] keep ] infer." "* Stack effect:" "( object -- object object )" }
"In general, combinators must be declared " { $link POSTPONE: inline } " so that we can infer the stack effects of words that call them with literal quotations."
$terpri
"Here is an example where the stack effect cannot be inferred:"
-{ $code ": foo 0 [ + ] ;" "[ foo reduce ] infer ." }
+{ $code ": foo 0 [ + ] ;" "[ foo reduce ] infer." }
"However if " { $snippet "foo" } " was declared " { $link POSTPONE: inline } ", everything would work, since the " { $link reduce } " combinator is also " { $link POSTPONE: inline } ", and the inferencer can see the literal quotation value at the point it is passed to " { $link call } ":"
-{ $example ": foo 0 [ + ] ; inline" "[ foo reduce ] infer ." "{ 1 1 }" } ;
+{ $example ": foo 0 [ + ] ; inline" "[ foo reduce ] infer." "* Stack effect:" "( object -- object )" } ;
ARTICLE: "inference-branches" "Branch stack effects"
"Conditionals such as " { $link if } " and combinators built on " { $link if } " present a problem, in that if the two branches leave the stack at a different height, it is not clear what the stack effect should be. In this case, inference throws a " { $link unbalanced-branches-error } "."
$terpri
"If all branches leave the stack at the same height, then the stack effect of the conditional is just the maximum of the stack effect of each branch. For example,"
-{ $example "[ [ + ] [ drop ] if ] infer ." "{ 3 1 }" }
-"The call to " { $link if } " takes one value from the stack, a generalized boolean. The first branch " { $snippet "[ + ]" } " has stack effect " { $snippet "{ 2 1 }" } " and the second has stack effect " { $snippet "{ 1 0 }" } ". Since both branches decrease the height of the stack by one, we say that the stack effect of the two branches is " { $snippet "{ 2 1 }" } ", and together with the boolean popped off the stack by " { $link if } ", this gives a total stack effect of " { $snippet "{ 3 1 }" } "." ;
+{ $example "[ [ + ] [ drop ] if ] infer." "* Stack effect:" "( object object object -- object )" }
+"The call to " { $link if } " takes one value from the stack, a generalized boolean. The first branch " { $snippet "[ + ]" } " has stack effect " { $snippet "( x x -- x )" } " and the second has stack effect " { $snippet "( x -- )" } ". Since both branches decrease the height of the stack by one, we say that the stack effect of the two branches is " { $snippet "( x x -- x )" } ", and together with the boolean popped off the stack by " { $link if } ", this gives a total stack effect of " { $snippet "( x x x -- x )" } "." ;
ARTICLE: "inference-recursive" "Stack effects of recursive words"
"Recursive words must declare a stack effect. When a recursive call is encountered, the declared stack effect is substituted in. When inference is complete, the inferred stack effect is compared with the declared stack effect."
$terpri
"Attempting to infer the stack effect of a recursive word which outputs a variable number of objects on the stack will fail. For example, the following will throw an " { $link unbalanced-branches-error } ":"
-{ $code ": foo ( seq -- ) dup empty? [ drop ] [ dup pop foo ] if" "[ foo ] infer ." }
+{ $code ": foo ( seq -- ) dup empty? [ drop ] [ dup pop foo ] if" "[ foo ] infer." }
"If you declare an incorrect stack effect, inference will fail also. Badly defined recursive words cannot confuse the inferencer." ;
ARTICLE: "inference-limitations" "Inference limitations"
"An inline recursive word must have a fixed stack effect in its base case. The following will not infer:"
{ $code
": foo ( quot ? -- ) [ f foo ] [ call ] if ; inline"
- "[ [ 5 ] t foo ] infer ."
+ "[ [ 5 ] t foo ] infer."
} ;
ARTICLE: "inference-custom" "Customizing inference behavior"
"The stack effect inference tool is used to check correctness of code before it is run. It is also used by the compiler to build a dataflow graph on which optimizations can be performed. Only words for which a stack effect can be inferred will compile."
$terpri
"The main entry point is a single word taking a quotation as input and returning a stack effect as output:"
-{ $subsection infer }
+{ $subsection infer. }
"The stack effect inference tool can also check stack effect declarations for corectness:"
{ $subsection "effect-declaration" }
"The following articles describe the implementation of the stack effect inference algorithm:"
IN: inference
-USING: compiler help kernel sequences ;
+USING: compiler help kernel sequences words ;
HELP: inference-error
{ $values { "msg" "an object" } }
{ $notes "See " { $link "shuffle-words" } " for retain stack usage conventions." } ;
HELP: infer
-{ $values { "quot" "a quotation" } { "effect" "a pair of integers" } }
-{ $description "Attempts to infer the quotation's stack effect, and outputs a pair holding the correct of data stack inputs and outputs for the quotation." }
+{ $values { "quot" "a quotation" } { "effect" "an instance of " { $link effect } } { "infer-vars" "an instance of " { $link inferred-vars } } }
+{ $description "Attempts to infer the quotation's stack effect and variable usage. For interactive testing, the " { $link infer. } " word should be called instead since it presents the output in a nicely formatted manner." }
+{ $errors "Throws an " { $link inference-error } " if stack effect inference fails." } ;
+
+HELP: infer.
+{ $values { "quot" "a quotation" } }
+{ $description "Attempts to infer the quotation's stack effect and variable usage, and prints this data to the default stream." }
{ $errors "Throws an " { $link inference-error } " if stack effect inference fails." } ;
HELP: dataflow
projects / factor.git / commitdiff