Prolog DCG Primer
Introduction
A Prolog definite clause grammar (DCG) describes
a sequence. Operationally, DCGs can be used
to parse, generate, complete and check
sequences manifested as lists.
| Video: |
|
DCGs are of great significance for Prolog: From a
historical perspective, Prolog originated from systems that were
designed for natural language processing, and a built-in mechanism
for efficient parsing that also preserves Prolog's logical
characteristics was one of the most important milestones in its
development. From a practical perspective, DCGs are frequently
used to describe lists because they are so convenient to use.
A DCG is defined by rules. A DCG rule has the form:
Head --> Body.
A rule's body consists of terminal, nonterminals, and
grammar goals. A terminal is a list, and stands for
the elements it contains. These elements are
terminal symbols of the grammar. A nonterminal
refers to a DCG or other grammar construct, and stands for the
elements it describes. A nonterminal therefore stands for a
sequence of terminal symbols. A grammar goal is
written in curly brackets as { Goal } and
is used to invoke Prolog goals within a grammar.
We use the nonterminal indicator A//N to
refer to the nonterminal A with
arity N. Note that // distinguishes it
from a
Prolog predicate indicator.
As an example of a DCG, let us describe sequences whose every element
is the atom a. We shall use the
nonterminal as//0 to refer to such sequences:
as --> [].
as --> [a], as.
The first rule states: The empty sequence is such a sequence. The second
rule uses the nonterminal (',')//2, which we read as
"and then". Therefore, the second rule states: A sequence
that contains as its first element the atom a and
then only atoms a is also such a sequence.
To invoke a grammar rule, we use Prolog's
built-in phrase/2 predicate. The first argument is,
syntactically, a DCG body. phrase(Body,
Ls) is true iff Body describes the
list Ls.
For example, let us use the single nonterminal as//0
to ask for all lists that it describes, by posting
the most general query:
?- phrase(as, Ls).
Ls = []
; Ls = [a]
; Ls = [a,a]
; Ls = [a,a,a]
; Ls = [a,a,a,a]
; ... .
Prolog lets us write lists of characters,
i.e., strings, very conveniently if the
Prolog flag double_quotes is set to chars, for
example by posting the query:
?- set_prolog_flag(double_quotes, chars).
true.
or by adding the following directive in your initialisation file
or program:
:- set_prolog_flag(double_quotes, chars).
We strongly recommend using this setting for better readability
of programs, queries and answers. In Scryer Prolog and
Tau Prolog, this is already the default setting.
With double_quotes set to chars, the list of
characters [a,a,a] can be written equivalently
as "aaa", and a Prolog system may therefore report the
solutions above equivalently and more compactly as:
?- phrase(as, Ls).
Ls = []
; Ls = "a"
; Ls = "aa"
; Ls = "aaa"
; Ls = "aaaa"
; ... .
Throughout this text, we assume that the Prolog
flag double_quotes is set to chars.
Examples of more specific queries and the system's answers:
?- phrase(as, "aaa").
true
; false.
?- phrase(as, "bcd").
false.
?- phrase(as, [a,X,a]).
X = a
; false.
Describing sequences with seq//1, seqq//1 and ... //0
Let us define the nonterminal seq//1 to describe a
sequence of elements. We use its single argument to refer to the
sequence that it describes, represented as a list:
seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).
Sample use case:
?- phrase(("Hello, ",seq(Cs),"!"), "Hello, all!").
Cs = "all"
; false.
Note that in cases where we use DCGs only to generate
lists, you might be tempted to define seq//1 as follows:
badseq(Ls) --> Ls.
This still works as expected in cases like:
?- phrase(badseq("abc"), Ls).
Ls = "abc".
However, it is still not a good idea for two reasons: First, it
cannot be used in the other direction and is thus not a pure
relation:
?- phrase(badseq(Ls), "abc").
error(instantiation_error,phrase/3).
Second, such a simplistic definition can be tricked into invoking
arbitrary code by specifying {Goal} as the argument, as
in:
?- phrase(badseq({halt}), _).
For these two reasons, it is better to use the definition
of seq//1 shown above to refer to arbitrary lists
with DCGs.
Using seq//1, we can define seqq//1 to describe
a sequence of sequences:
seqq([]) --> [].
seqq([Es|Ess]) -->
seq(Es),
seqq(Ess).
Sample use:
?- phrase(seqq(["ab","cd","ef"]), Ls).
Ls = "abcdef".
This is an elegant way to describe the concatenation of
arbitrarily many lists.
It is sometimes useful to describe "any sequence at all", and we can
do this with the nonterminal ... //0 which is
equivalent to seq(_):
The grammar construct ('|')//2 and its
equivalent (;)//2 correspond to the Prolog control
structure (;)/2 and are read as "or". When parsing
with DCGs, using ('|')/2 is preferable over (;)//2
due to existing conventions for writing grammars.
seq//1, seqq//1 and ... //0 are very
versatile nonterminals and can be used to elegantly solve many
tasks that involve reasoning over lists. For example, the last
element of a list can be described with:
?- phrase((...,[Last]), "hello").
Last = o
; false.
As another example, consecutively repeated elements in a list can be described with:
?- phrase((...,[E,E],...), Ls).
Ls = [E,E]
; Ls = [E,E,_A]
; Ls = [E,E,_A,_B]
; Ls = [E,E,_A,_B,_C]
; ... .
Using iterative deepening, we obtain a fair enumeration of answers:
?- length(Ls, _), phrase((...,[E,E],...), Ls).
Ls = [E,E]
; Ls = [E,E,_A]
; Ls = [_A,E,E]
; Ls = [E,E,_A,_B]
; Ls = [_A,E,E,_B]
; Ls = [_A,_B,E,E]
; ... .
In Scryer Prolog, seq//1, seqq//1
and ... //0 are provided
by library(dcgs).
List reversal, palindromes and other exercises
When reasoning about lists or solving exercises involving lists,
consider using DCGs for convenience.
| Video: |
|
For example, the reversal of a list can be described with:
reversal([]) --> [].
reversal([L|Ls]) --> reversal(Ls), [L].
Sample query and answer:
?- phrase(reversal("abcd"), Ls).
Ls = "dcba".
As another example, a palindrome can be described with:
palindrome --> [].
palindrome --> [_].
palindrome --> [E], palindrome, [E].
This definition can be used to generate, to complete
and to check palindromes. For example:
?- phrase(palindrome, "hellolleh").
true
; false.
?- phrase(palindrome, Ls).
Ls = []
; Ls = [_A]
; Ls = [_A,_A]
; Ls = [_A,_B,_A]
; Ls = [_A,_B,_B,_A]
; ... .
Challenge: Define palindrome//0
using reversal//1. Provide two different definitions.
Relating trees to lists
Let us now use a DCG to relate a binary tree to the in-order
sequence of its node names. Let us assume a binary tree consists
of leaves represented by the atom nil and inner
nodes of the form node(Name, Left, Right),
where Left and Right are themselves binary
trees. To obtain the in-order sequence of node names, consider:
tree_nodes(nil) --> [].
tree_nodes(node(Name, Left, Right)) -->
tree_nodes(Left),
[Name],
tree_nodes(Right).
Example:
?- phrase(tree_nodes(node(a, node(b, nil,
node(c, nil, nil)),
node(d, nil, nil))), Ns).
Ns = "bcad".
You can obtain other orders by moving the
terminal [Name] in the DCG body.
Left recursion
Conversely, given a sequence of node names, what are the trees
that yield this sequence:
?- phrase(tree_nodes(Tree), "abcd").
Tree = node(a,nil,node(b,nil,node(c,nil,node(d,nil,nil))))
; % (nontermination)
The system yields one (correct) solution, then loops. This is
because the grammar is left-recursive: We recursively refer to a
nonterminal (tree_nodes//1) before anything else. To be
able to use this grammar for finding all matching trees, we need
to encode that for the second rule to apply, at least one list
element must be available since the rule contains exactly one
terminal, and we need to check this in advance to avoid unbounded
recursion. We can do this by introducing two additional arguments
that let us limit the number of rule applications to the given
list's length:
tree_nodes(nil, Ls, Ls) --> [].
tree_nodes(node(Name, Left, Right), [_|Ls0], Ls) -->
tree_nodes(Left, Ls0, Ls1),
[Name],
tree_nodes(Right, Ls1, Ls).
Each respective pair of additional arguments describes a
so-called list difference. To understand this method
and its associated terminology, consider for example the
pair Ls0 and Ls1. We can interpret
the difference of these lists as describing the list of
elements that are consumed by the first recursive invocation
of tree_nodes//3 in this example. Analogously, the
difference of the lists Ls1 and Ls is the
list of elements consumed by the second invocation. And the
difference between the lists that occur in the head, i.e.,
that of [_|Ls0] and Ls, describes the list of
elements that are consumed by the entire second rule.
| Video: |
|
Of course, difference is to be understood in
a symbolic sense in these cases, not in an arithmetic
sense. For example, the difference between the
lists [A,B,C] and [C]
is [A,B], the difference between [X,Y|Ls]
and Ls is [X,Y], and the difference
between Ls and Ls is []. By
reasoning about such list differences via argument
pairs, we can compose and decompose entire lists by reasoning
about their sublists. This powerful method is in fact also the
key idea that underlies the
common transformation of DCGs to
Prolog predicates. In cases where you are using it, consider
using DCGs instead. In the present case, we are using list
differences explicitly because we are using
them within DCGs.
In the literature, you will also encounter the
term "difference list". However, this terminology is
misleading: We are not talking about—as the name may
suggest—a special kind of list. The additional
arguments are completely
ordinary lists or partial lists.
It is their differences that matter especially in such
cases.
When working with list differences, you may be tempted to
pass around each pair as a single argument, for example as
compound terms like Ls0-Ls1 or Ls0/Ls1. However,
this is not advisable, primarily because you will likely run into
conflicts with other predicates and DCG expansions, and
secondarily because it incurs performance overhead for
constructing, decomposing and managing these compound terms.
Example query:
?- Ns = "abcd", phrase(tree_nodes(Tree, Ns, _), Ns).
Ns = "abcd", Tree = node(a,nil,node(b,nil,node(c,nil,node(d,nil,nil))))
; Ns = "abcd", Tree = node(a,nil,node(b,nil,node(d,node(c,nil,nil),nil)))
; Ns = "abcd", Tree = node(a,nil,node(c,node(b,nil,nil),node(d,nil,nil)))
; ... .
Another option to parse with left-recursive grammars is to use
your Prolog system's tabling
mechanism. Combining tabled execution with DCGs
yields packrat parsing; an interesting paper about
this topic
is DCGs
+ Memoing = Packrat Parsing, But is it worth it? by Ralph
Becket and Zoltan Somogyi.
Semicontext notation
Using semicontext notation, in now outdated terminology
also called pushback lists or right-hand context, we
can make statements about remaining elements. Operationally
speaking, we can insert list elements that were initially not in
the list that is being parsed. A DCG rule of the form:
Head, [T1,...,Tn] --> Body.
can be read operationally as: parse the list
using Body, then prepend the
terms T1, ..., Tn to the remaining list.
For example:
nt1, [b] --> [a].
nt2 --> [b].
The body of nt1//0 describes a list whose single element
is the atom a. Operationally, after nt1//0
has consumed the atom a in a list that is being
parsed, it inserts the atom b in front of the
remaining list. nt2//0 describes a list whose single
element is the atom b. The following query therefore
succeeds, since nt2//0 consumes the atom b,
which is left in the list after nt1//0 succeeds:
?- phrase((nt1,nt2), "a").
true.
We can also use nt1//0 in isolation. However, the following query
fails since phrase/2 only succeeds if all list elements
are consumed by the given DCG body:
?- phrase(nt1, "a").
false.
The list difference version phrase/3 shows what remains
after nt1//0 succeeds:
?- phrase(nt1, "a", Rest).
Rest = "b".
As expected, the atom b remains in the list.
Using semicontext notation, we can implement look ahead,
which lets us inspect the next element in the list without
removing it. Operationally, we first remove it and then push it
back:
look_ahead(T), [T] --> [T].
Example:
?- phrase(look_ahead(T), "a", Rest).
Rest = "a", T = a.
Implicitly passing states around
Semicontext notation is also useful to
implicitly pass around a state representation that is only
accessed and changed by a subset of rules. For example, let us
count the leaves in a binary tree with the above
presentation. Without using DCGs, we can relate a tree to the
number of its leaves as follows:
num_leaves(Tree, N) :-
num_leaves_(Tree, 0, N).
num_leaves_(nil, N0, N) :- N #= N0 + 1.
num_leaves_(node(_,Left,Right), N0, N) :-
num_leaves_(Left, N0, N1),
num_leaves_(Right, N1, N).
Notice that in the second clause of num_leaves_/3, the
accumulator is only passed through
as N0, N1, ..., N and not
modified directly. When you encounter such a pattern, consider
using DCG notation to pass around the arguments implicitly.
In this concrete case, the state we shall pass around is a
single integer denoting the number of leaves encountered so far.
To increment the state, we use
Prolog's declarative integer
arithmetic like above. To invoke a Prolog predicate from
within a DCG body, we use the DCG language
construct {}//1. Operationally, when the
construct {Goal} is encountered in a DCG
body, Goal is called as a Prolog goal. Since
a DCG must always describe a list, we wrap the state into a
list and thus describe a list containing a single element. The
initial state is again sensibly specified as 0, and the
number of leaves is given by the remaining list element
after num_leaves_//1 succeeds:
num_leaves(Tree, N) :-
phrase(num_leaves_(Tree), [0], [N]).
num_leaves_(nil), [N] --> [N0], { N #= N0 + 1 }.
num_leaves_(node(_,Left,Right)) -->
num_leaves_(Left),
num_leaves_(Right).
Notice that the second rule of num_leaves_//1 makes no
reference at all to the state, since the number of leaves is not
modified when an inner node is processed.
Example query:
?- num_leaves(node(a,node(b,nil,nil),
node(c,nil,
node(d,nil,nil))), N).
N = 5.
The following nonterminals are useful for describing states with
DCGs:
state(S), [S] --> [S].
state(S0, S), [S] --> [S0].
Note: Code in grey boxes may be useful for you to reuse in
your own projects.
The nonterminal state(S) can be read as: "The current
state is S". The nonterminal state(S0, S) can be
read as: "The current state is S0, and henceforth it
is S".
Using state//2, you can write num_leaves_//1 as:
num_leaves_(nil) --> state(N0, N), { N #= N0 + 1 }.
num_leaves_(node(_,Left,Right)) -->
num_leaves_(Left),
num_leaves_(Right).
This approach is readily generalized to multiple states that are
threaded through: You can for example use a
term s(S1,S2,...,Sn) in such cases.
Reading from files
In Scryer Prolog, SICStus Prolog and SWI-Prolog, DCGs can be
transparently applied to files using Ulrich
Neumerkel's library(pio).
When you need to process input from files, first write a DCG that
describes the input. This lets you test the DCG in a pure way
using phrase/2, and then apply the DCG to files too
by simply using phrase_from_file/2 instead
of phrase/2.
| Video: |
|
In our first example, we read a whole file to a list of
characters. This is very easy to do with seq//1 as
defined above. For example, to read the contents of the
file dcg.html to a list of characters, we use:
?- phrase_from_file(seq(Chars), "dcg.html").
Chars = "<!DOCTYPE html>\n<ht ..."
; false.
As another example, consider the following DCG that
uses seq//1 to refer to a subsequence of characters:
like(What) --> "I like ", seq(What), ".", ... .
As before, we can use this DCG to parse a given list of characters:
?- phrase(like(What), "I like it. Anything can follow!").
What = "it"
; false.
As expected, What is unified with the atoms i
and t.
Moreover, using library(pio) and
its phrase_from_file/2, we can transparently parse from a
file with the same DCG. Assume that the
file like.txt starts with the string "I like it."
?- phrase_from_file(like(What), "like.txt").
What = "it"
; false.
Again, What is unified with the atoms i
and t.
Pure input via library(pio) can be implemented in such a
way that it uses memory efficiently when parsing files: First, the
file can be read lazily, reading only as much as is needed.
Second, file contents can be very compactly represented in memory
if your Prolog system supports an
efficient representation of lists of
characters. Third, file contents that are no longer relevant for
parsing can be reclaimed automatically if your Prolog system
satisfies the properties outlined
in Precise
Garbage Collection in Prolog.
For these reasons, library(pio) is well-suited
also for parsing large files.
Parsing tricks and techniques
When parsing, we often want to consume tokens greedily,
meaning that the longest match should be given priority. We
can do this by ordering the DCG rules accordingly. For
example, the following DCG describes a list of whitespace
characters in such a way that the longest such sequence is the
first solution, using char_type/2
from library(charsio) for character classification:
ws --> [W], { char_type(W, whitespace) }, ws.
ws --> [].
Identifiers that must start with a letter and may contain
either letters or digits can be parsed by applying this technique:
identifier([A|As]) --> [A], { char_type(A, alpha) }, symbol_r(As).
symbol_r([A|As]) --> [A], { char_type(A, alnum) }, symbol_r(As).
symbol_r([]) --> [].
As another technique that is sometimes useful for parsing, here
are DCG rules that describe a list of lines that are
terminated by line feed or end of file:
lines([]) --> call(eos), !.
lines([L|Ls]) --> line(L), lines(Ls).
line([]) --> ( "\n" | call(eos) ), !.
line([C|Cs]) --> [C], line(Cs).
eos([], []).
The nonterminal call//1 is used to call a Prolog
predicate in such a way that the implicit DCG arguments are made
available as explicit arguments. We need this to describe the
condition "end of string". The grammar construct
!//0 is used like the corresponding Prolog control
structure.
We can use these definitions to obtain the contents of a file as
a list of lines for further reasoning:
?- phrase_from_file(lines(Ls), "like.txt").
Ls = ["I like it. Anythi ..."].
Note: eos/2 is comparatively rarely needed. In the
above case it is used because anything else is the
beginning of a new line. Typically, you can more directly express
what you want to describe, and phrase/2
and phrase_from_file/2 only succeed if
the complete list or file matches the description.
Therefore, it is typically not necessary to explicitly refer to
"end of the string".
Describing output
DCGs are also useful for describing output, because output
is a list of characters.
In library(format),
Scryer Prolog provides the nonterminal format_//2 to
declaratively describe output based on a format string
that defines the layout of specified arguments.
| Video: |
|
For example, we can describe a table with format_//2:
table -->
row([this,is,a]),
row([very,nice,table]).
row(Ls) --> format_("~t~w~7+~t~w~7+~t~w~7+~n", Ls).
Sample query and its results:
?- phrase(table, Ts).
Ts = " this is ...".
An important advantage of this declarative way to describe output
is that we can write test cases and reason about it:
It is quite hard to reason about output that only appears on the
system terminal, with no other tangible manifestation. In
contrast, it is easy to state properties that must hold about a
list of characters.
When needed, we can show the table on the terminal with a single
call of format/2:
?- phrase(table, Ts), format("~s", [Ts]).
this is a
very nice table
Ts = " this is ...".
Implementation
To see how DCGs are internally implemented in Scryer Prolog, we
can use listing/1 from library(format). For
example, to see the actual source code of num_leaves_//1,
we declare the nonterminal dynamic via the dynamic/1
directive, and use:
?- listing(num_leaves_//1).
num_leaves_(nil,A,B) :-
state(C,D,A,E),
D#=C+1,
E=B.
num_leaves_(node(A,B,C),D,E) :-
num_leaves_(B,D,F),
num_leaves_(C,F,E).
We see that internally, the two DCG rules
of num_leaves_//1 were translated into Prolog rules with
two additional arguments, following mechanical rewriting steps.
The translation of DCGs to Prolog code is done
by term_expansion/2, a mechanism analogous
to macros in other languages.
For portability, it is best not to rely on a particular expansion
method. Instead, use semicontext notation to refer to states and
always use the phrase/[2,3] interface to invoke a DCG.
This way, a Prolog system is free to apply a different expansion
method that may be more efficient. For example, the last two
arguments may as well be swapped and allow more efficient
predicate calls this way due to specifics of a particular virtual
machine.
Using DCGs
Consider using DCGs if you are:
- describing a list
- reading from a file
- passing around a state representation that only a few
predicates actually use or modify.
In every serious Prolog program, you will find many opportunities to
use DCGs due to some subset of the above reasons.
Let us study one side-by-side comparison of a regular Prolog
predicate and an equivalent DCG nonterminal to recall several
important aspects of using DCGs and make some additional
observations. We take the well-known Prolog
predicate include/3 as an example:
| regular Prolog |
Prolog DCG |
include(Goal, List, Included) :-
include_(List, Goal, Included).
include_([], _, []).
include_([L|Ls], Goal, Included0) :-
( call(Goal, L) ->
Included0 = [L|Included]
; Included0 = Included
),
include_(Ls, Goal, Included).
|
include(Goal, List, Included) :-
phrase(include_(List, Goal), Included).
include_([], _) --> [].
include_([L|Ls], Goal) -->
( { call(Goal, L) } ->
[L]
; []
),
include_(Ls, Goal).
|
Usage example for both versions:
?- include(integer, [a,b,c,1,2,e], Is).
Is = [1, 2].
We recall and note in particular:
- phrase/2 must of course be used to refer to a DCG
nonterminal within a regular Prolog predicate
- conversely, {}//1 is used to call a regular Prolog goal within a DCG
- the DCG version needs fewer explicit arguments, making it slightly easier to read and understand
- although it is strongly related to the previous point, it is
still worth mentioning explicitly that the DCG version also
refers to fewer variables
- using a DCG makes immediately clear that a list is
being described.
Take your time and see for yourself which of the two versions you
find easier to read and understand.
Some applications of DCGs that you can download from this site and study:
- markov.pl uses DCGs to
describe output of a Markov chain
- Lisprolog uses DCGs to parse Lisp expressions and to implicitly thread through the state of the environment
- Tist uses DCGs for all of the above
reasons throughout the document
- The comp.lang.prolog FAQ are described with a DCG.
Current developments
DCGs are currently being considered for inclusion in the Prolog
ISO standard.
See
ISO
Prolog works by Ulrich Neumerkel for more information.
DCG notation is similar to monads which have been adopted as
one of the most versatile among several competing formalisms in
functional programming languages like Haskell. Other
programming languages may also benefit from such constructs.
More about Prolog
Main page


Welcome to MareNostrums Web Server
An IAG+L project
Tip:
Collection?constrain1=value1&constrain2=values2... And do not forget your card at home!
Go, Johnny Go!


A simple javaScript calculator by John Otu | @john_otu using Jose de Jong's math.js, jQuery and Bootstrap.


Tupperware Brands Confidence Center
Tupperware created this center in order to celebrate and honor the company’s heritage as well as to convey and shine a spotlight on…
At SQUAREFACTOR we worked both directly with clients as well as augmenting the team of many full service ad agencies. If need be we would even identify ourselves as part of an existing team. The range of project worked on was quite broad. Work included websites, banner ads, mobile, emails, experiential, games, product builders, hardware integration and more. In addition to the client work I also ran the business with my partners.
Below you will find a small sampling of work completed at SQUAREFACTOR.
Tupperware created this center in order to celebrate and honor the company’s heritage as well as to convey and shine a spotlight on…
In order to help customers gain an understanding of the amazing 3M technologies, a new 3M Innovation Center was constructed in St. Paul Minnesota.
Motorola wanted to provide tattoos and etching for several of their popular phones at the store…
Bose was developing a sound system for the Ferrari Scaglietti and they needed a way to prototype…
The Witte Museum, San Antonio’s premiere museum of South Texas history, culture, and natural science…
These Toyota banners were originally done in Flash and needed to be converted to HTML…


THE SHAWSHANK REDEMPTION A film review by Mark R. Leeper Copyright 1994 Mark R. Leeper
Capsule review: This is a beautifully told and photographed story of a man who transforms an entire prison through his humanity. With acting and production values uniformly excellent, this film works on both the literal level and as an allegory. It could well make it to the status of being a classic like ONE FLEW OVER THE CUCKOO'S NEST. Rating: low +3 (-4 to +4)
I never read Stephen King's 1982 novella "Rita Hayworth and the Shawshank Redemption," part of his collection DIFFERENT SEASONS. But it is difficult to believe that THE SHAWSHANK REDEMPTION could be very accurate to this non-horror King story. As much as I like King, it is difficult to believe he wrote a story as good as this film adaptation. The theme is the strength of humanity over brutality--much the same theme as SCHINDLER'S LIST--and Frank Darabont has crafted a film, writing and directing, that compares favorably with ONE FLEW OVER THE CUCKOO'S NEST. There is a lot going on in THE SHAWSHANK REDEMPTION, and parts will remind viewers of such diverse films as BILLY BUDD, OF MICE AND ME, and even DEAD POETS SOCIETY. The film is another parable, following on the heels of FORREST GUMP. But where GUMP was content to create a period feel and present a message of "Just be simple and let everything happen to you," SHAWSHANK is a much better piece of storytelling and has just the opposite message, "Stand up and take control of your life. Get busy living or get busy dying." Forrest Gump would last about one week in Shawshank Prison. Andy Dufresne, the focus of this story, is a survivor. And he is more.
As the film opens Andy Dufresne (played by Tim Robbins) is about to murder his wife and her lover. On the witness stand he denies that he ever completed the crime. But if he didn't, somebody else did, and all the evidence points to Andy. The sentence is two consecutive life terms in Shawshank Penitentiary--not much of a life for a banker. The film follows Andy's life in prison.  Worse. But a chance comment by the most brutal of the guards, Captain Hadley (Clancy Brown), gives Andy an idea of how with one stroke he can get on the good side of guards and prisoners alike. And among the prisoners he particularly want to be friends with Red, the prison scrounge. Red is useful to have as a friend, not only because he is a man of character whom the other prisoners respect, not only because he can get Andy what he needs to make his life a little easier, but also because he is the story narrator and it is never a bad idea in a film to be on the good side of the narrator. In the book Red was Irish, but here he is played with tremendous dignity by Morgan Freeman.
In the years that pass in Shawshank--and they do pass quickly even if the film has a leisurely pace--Andy finds ways to make himself indispensable to the sadistic, Bible-thumping Warden Norton (Bob Gunton) and the guards, always winning more concessions to make life better for the inmates. Through Red's and Andy's eyes we see the ironies of prison life. But there is much more to the story than that of a goody-goody in prison, and the plot has interesting complications. A surprisingly long segment of the film is devoted to one of the minor prisoners released to the outside world only to find adjustment a difficult proposition. But the investment of screen time for this subplot pays off later in the film.
This is a film with excellent production values almost without exception. Prison movies are an entire genre, I suppose, and in the hands of a less skilled photographer Shawshank could have come off as just dismal as any other prison film without any particular visual interest. But the director of photography was Roger Deakins whose films include MOUNTAINS OF THE MOON, HOMICIDE, BARTON FINK, and THE HUDSUCKER PROXY. He is a man with a very good eye for the visual in period pieces and from the first scene of guards on the walls of Shawshank his photography has excellent composition and detail. Production design is by Oscar-winner Terence Morgan, who did design for such diverse films as DR. ZHIVAGO, THE HUNT FOR RED OCTOBER, and CLEAR AND PRESENT DANGER. Between the two we see a prison that visually captures our interest. This is no small feat for a prison picture. To some extent, Shawshank is so well photographed, it gives the film almost a poetic feel rather than one of realism, but for a longish film that is the way to go. The one serious problem visually with the production is in makeup. The film covers 19 years from 1947 to 1966 under conditions that should age people quickly. A little greying in the hair of the main characters seems the only concession made to the aging process. More of the period feel is added by having the film narrated. That is more in the style of filmmaking of the 40s and 50s.
This is a film that takes its time at 142 minutes, but it does a lot in that time. My rating is a low +3 on the -4 to +4 scale.
Mark R. Leeper<EMAIL_ADDRESS>.
The review above was posted to the
rec.arts.movies.reviews newsgroup (de.rec.film.kritiken for German reviews).
The Internet Movie Database accepts no responsibility for the contents of the
review and has no editorial control. Unless stated otherwise, the copyright
belongs to the author.
Please direct comments/criticisms of the review to relevant newsgroups.
Broken URLs inthe reviews are the responsibility of the author.
The formatting of the review is likely to differ from the original due
to ASCII to HTML conversion.
Related links: index of all rec.arts.movies.reviews reviews


|
Fusion3D
Version 6.04
|
Qt dialog for moving to a new location or reading the current location. More...
#include <dialogLocJump.h>
Public Member Functions | |
| dialogLocJump (QWidget *parent=Q_NULLPTR) | |
| ~dialogLocJump () | |
| int | register_coord_system (gps_calc_class *gps_calc_in) |
| Register the common gps_calc_class for defining the current coordinate systems and transformations between them. More... | |
| Public Member Functions inherited from Ui_dialogLocJump | |
| void | setupUi (QDialog *dialogLocJump) |
| void | retranslateUi (QDialog *dialogLocJump) |
Additional Inherited Members | |
| Public Attributes inherited from Ui_dialogLocJump | |
| QRadioButton * | mgrsButton |
| QRadioButton * | utmButton |
| QRadioButton * | latButton |
| QLabel * | label |
| QPushButton * | cancelButton |
| QLineEdit * | longEdit |
| QLineEdit * | latEdit |
| QLabel * | label_2 |
| QLabel * | label_3 |
| QLineEdit * | northEdit |
| QLineEdit * | eastEdit |
| QLineEdit * | mgrsnEdit |
| QLineEdit * | mgrseEdit |
| QLineEdit * | mgrsxEdit |
| QLineEdit * | mgrsZoneLatEdit |
| QLineEdit * | utmZoneLatEdit |
| QPushButton * | JumpButton |
| QLineEdit * | mgrsZonLonEdit |
| QLineEdit * | utmZoneLonEdit |
| QLabel * | label_4 |
| QLabel * | label_5 |
Qt dialog for moving to a new location or reading the current location.
Qt menu accepts and outputs location in Lat-Lon, UTM (m) or MGRS.
| dialogLocJump::dialogLocJump | ( | QWidget * | parent = Q_NULLPTR | ) |
| dialogLocJump::~dialogLocJump | ( | ) |
| int dialogLocJump::register_coord_system | ( | gps_calc_class * | gps_calc_in | ) |
Register the common gps_calc_class for defining the current coordinate systems and transformations between them.
A single gps_calc_class class should be held in common over all classes that need coordinate systems or transforms and should do all transforms.


class: center, middle ### W4995 Applied Machine Learning # Linear models for Regression 01/31/18 Andreas C. Müller ??? So today we'll talk about linear models for regression. You're probably familiar with some of the basics, and that's where we'll start. But we'll also look into how to tune these models, what the trade-offs are, and some more complex techniques. TODO: SVR to robust models? Move path algorithms into this lecture instead of robust regression? Add more preprocessing and scaling to this lecture? dimensionality -> model complexity? --- class:center # Linear Models for Regression ![:scale 50%](images/linear_regression_1d.png) $$\hat{y} = w^T \mathbf{x} + b = \sum_{i=1}^p w_i x_i +b$$ ??? Predictions in all linear models for regression are of the form shown here: It's an inner product of the features with some coefficient or weight vector w, and some bias or intercept b. In other words, the output is a weighted sum of the inputs, possibly with a shift. here i runs over the features and x_i is one feature of the data point x. These models are called linear models because they are linear in the parameters w. The way I wrote it down here they are also linear in the features x_i. However, you can replace the features by any non-linear function of the inputs, and it'll still be a linear model. There are many differnt linear models for regression, and they all share this formula for making predictions. The difference between them is in how they find w and b based on the training data. --- # Ordinary Least Squares $$\hat{y} = w^T \mathbf{x} + b = \sum_{i=1}^p w_i x_i +b $$ `$$\min_{w \in \mathbb{R}^p} \sum_{i=1}^p ||w^T\mathbf{x}_i - y_i||^2$$` Unique solution if $\mathbf{X} = (\mathbf{x}_1, ... \mathbf{x}_n)^T$ has full column rank. ??? The most straight-forward solution that goes back to Gauss is ordinary least squares. In ordinary least squares, find w and b such that the predictions on the training set are as accurate as possible according the the squared error. That intuitively makes sense: we want the predictions to be good on the training set. If there is more samples than features (and the samples span the whole feature space), then there is a unique solution. The problem is what's called a least squares problem, which is particularly easy to optimize and get the unique solution to. However, if there are more features than samples, there are usually many perfect solutions that lead to 0 error on the training set. Then it's not clear which solution to pick. Even if there are more samples than features, if there are strong correlations among features the results might be unstable, and we'll see some examples of that soon. Before we look at examples, I want to introduce a popular alternative. --- # Ridge Regression `$$ \min_{w \in \mathbb{R}^p} \sum_{i=1}^n ||w^T\mathbf{x}_i - y_i||^2 + \alpha ||w||^2 $$` Always has a unique solution. Tuning parameter alpha. ??? In Ridge regression we add another term to the optimization problem. Not only do we want to fit the training data well, we also want w to have a small squared l2 norm or squared euclidean norm. The idea here is that we're decreasing the "slope" along each of the feature by pushing the coefficients towards zero. This constraings the model to be more simple. So there are two terms in this optimization problem, which is also called the objective function of the model: the data fitting term here that wants to be close to the training data according to the squared norm, and the prenalty or regularization term here that wants w to have small norm, and that doesn't depend on the data. Usually these two goals are somewhat opposing. If we made w zero, the second term would be zero, but the predictions would be bad. So we need to trade off between these two. The trade off is problem specific and is specified by the user. If we set alpha to zero, we get linear regression, if we set alpha to infinity we get a constant model. Obviously usually we want something in between. This is a very typical example of a general principle in machine learning, called regularized empirical risk minimization. --- # (regularized) Empirical Risk Minimization `$$ min_{f \in F} \sum_{i=1}^n L(f(\mathbf{x}_i), y_i) + \alpha R(f) $$` ??? FIXME pointers data fitting / regularization! Many models in machine learning, like linear models, SVMs and neural networks follow the general framework of empirical risk minimization, which you can see here. We formulate the machine learning problem as an optimization problem over a family of functions. In our case that was the family of linear functions parametrized by w and b. The minimization problem consists of two parts, the data fitting part and the model complexity part. The data fitting part says that the predictions mad eby our functions should be accurate according to some loss L. For our regression problems that was the squared loss. The model complexity part says that we prefer simple models and penalizes complicated f. Most machine learning algorithms can be cast into this, with a particular choice of family of functions f, loss function L and regularizer R. And most of machine learning theory is build around this framework. People proof for differnt choices of F and L and R that if you minimize this, you'll be able to generalize well. And that makes intuitive sense. To do well on the test set, we definitely want to do reasonably well on the training set. We don't expect that we can do better on a test set than the training set. But we also want to minimize the performance difference between training and test set. If we restrict our model to be simple via the regularizer R, we have better chances of the model generalizing. --- # Reminder on model complexity ![:scale 80%](images/overfitting_underfitting_cartoon_full.png) ??? I hope this sounds familiar from what we talked about last time. This is a particular way of dealing with overfitting and underfitting. For this framework in general, or for ridge regression in particular, trading off the data fitting and the regularization changes the model complexity. If we set alpha high we restrict the model, and we will be on the left side of the graph. If we make alpha small, we allow the model to fit the data more, and we're on the right side of the graph. --- # Boston Housing Dataset ![:scale 70%](images/boston_housing_scatter.png) .smaller[ ```python print(X.shape) print(y.shape) ``` ``` (506, 13) (506,) ``` ] ??? Ok after all this pretty abstract talk, let's make this concrete. Let's do some regression on the boston housing dataset. After the last homework you're hopefully familiar with it. The idea is to predict prices of property in the boston area in different neighborhoods. This is a dataset from the 70s I think, so everything is pretty cheap. Most of the features you can see are continuous, with the exception of the charlston river variable which says whether the neighborhood is on the river. Keep in mind that this data lives in a 13 dimensional space and these univariate plots only look at 13 different projections of the data, and can't capture any of the interactions. But still we can see that the price clearly depends on some of these variables. It's also pretty clear that the dependency is non-linear for some of the variables. We'll still start with a linear model, because its a very simple class of models, and I'd always star approaching any model from the simplest baseline. In this case it's linear regression. We're having 506 samples and 13 features. We have much more samples than features. Linear regression should work just fine. Also it's a tiny dataset, so basically anything we'll try will run instantaneously, which is also good to keep in mind. Another thing that you can see in this graph is that the features have very different scales. Here's a box plot that shows that even more clearly. --- ![:scale 80%](images/boston_scaling.png) ??? That's something that will trip up the distance based models models we talked about last time, as well as the linear models we're talking about today. For the penalized models the different scales mean that different features are penalized differently, which you usually want to avoid. Usually there is no particular semantics attached to the fact that one feature has different magnitutes than another. We could measure something in inches instead of miles, and that would change the outcome of the model. That's certainly not something we want. A good idea is to scale the data to get rid of this effect. We'll talk about that and other preprocessing methods in-depth on Wednesday next week. Today I'm mostly gonna ignore this. But let's get started with Linear Regression --- class: middle, spacious ```python from sklearn.linear_model import LinearRegression from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split( X, y, random_state=0) np.mean(cross_val_score(LinearRegression(), X_train, y_train, cv=10)) ``` ``` 0.717 ``` ```python np.mean(cross_val_score(Ridge(), X_train, y_train, cv=10)) ``` ``` 0.715 ``` ??? So here are the --- # Coefficient of determination R^2 `$$ R^2(y, \hat{y}) = 1 - \frac{\sum_{i=0}^{n - 1} (y_i - \hat{y}_i)^2}{\sum_{i=0}^{n - 1} (y_i - \bar{y})^2} $$` `$$ \bar{y} = \frac{1}{n} \sum_{i=0}^{n - 1} y_i$$` Can be negative for biased estimators - or the test set! ??? --- # Scaling (if you want) ```python from sklearn.linear_model import Ridge from sklearn.preprocessing import StandardScaler X, y = boston.data, boston.target X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0) scaler = StandardScaler() scaler.fit(X_train) X_train_scaled = scaler.transform(X_train) ridge = Ridge().fit(X_train_scaled, y_train) X_test_scaled = scaler.transform(X_test) ridge.score(X_test_scaled, y_test) ``` ??? If you want to scale the data, you can use StandardScaler for that. It makes the mean zero and the standard deviation one. It's an unsupervised model, so it only takes the data X_train to fit. Fitting just means computing mean and standard devitation. Then, we can scale the data using the transform method. Make sure that you fit the data only on the training set, and then transform the training and the test set. If you want to use scaling inside cross-validation, it's a little bit more tricky. As I said, more details next wednesday. I'm just mentioning this here because it might come in handy for the homework. Ok but so let's come back to the Ridge model. Above we just used the default setting for the parameter alpha, which is one. This is a reasonable default, but there is no reason why this should give us the optimum generalization performance on this problem. So it's a good idea to adjust the parameter. As we saw on Monday, we can easily do that with gridsearchCV. --- .smallest[ ```python from sklearn.model_selection import GridSearchCV param_grid = {'alpha': np.logspace(-3, 3, 13)} print(param_grid) ``` ``` {'alpha': array([ 0.001, 0.003, 0.01, 0.032, 0.1, 0.316, 1., 3.162, 10., 31.623, 100., 316.228, 1000.])} ``` ```python grid = GridSearchCV(Ridge(), param_grid, cv=10) grid.fit(X_train, y_train) ``` ] .center[ ![:scale 60%](images/ridge_alpha_search.png) ] ??? --- # Adding features ```python from sklearn.preprocessing import PolynomialFeatures, scale poly = PolynomialFeatures(include_bias=False) X_poly = poly.fit_transform(scale(X)) print(X_poly.shape) X_train, X_test, y_train, y_test = train_test_split(X_poly, y) ``` ``` (506, 104) ``` ```python np.mean(cross_val_score(LinearRegression(), X_train, y_train, cv=10)) ``` ``` 0.74 ``` ```python np.mean(cross_val_score(Ridge(), X_train, y_train, cv=10)) ``` ``` 0.76 ``` ??? --- .center[ ![:scale 60%](images/ridge_alpha_search_poly.png) ] .smaller[ ```python print(grid.best_params_) print(grid.best_score_) ``` ``` {'alpha': 31.6} 0.83 ``` ] ??? --- # Plotting coefficient values (LR) ```python lr = LinearRegression().fit(X_train, y_train) plt.scatter(range(X_poly.shape[1]), lr.coef_, c=np.sign(lr.coef_), cmap="bwr_r") ``` .center[ ![:scale 55%](images/lr_coefficients_large.png) ] ??? --- # Ridge Coefficients ```python ridge = grid.best_estimator_ plt.scatter(range(X_poly.shape[1]), ridge.coef_, c=np.sign(ridge.coef_), cmap="bwr_r") ``` .center[ ![:scale 60%](images/ridge_coefficients.png) ] ??? --- ```python ridge100 = Ridge(alpha=100).fit(X_train, y_train) ridge1 = Ridge(alpha=1).fit(X_train, y_train) plt.figure(figsize=(8, 4)) plt.plot(ridge1.coef_, 'o', label="alpha=1") plt.plot(ridge.coef_, 'o', label="alpha=14") plt.plot(ridge100.coef_, 'o', label="alpha=100") plt.legend() ``` .center[ ![:scale 60%](images/ridge_coefficients_alpha.png) ] ??? --- # Coefficient Paths ![:scale 90%](images/ridge_coefficient_paths.png) ??? --- # Learning Curves ![:scale 90%](images/ridge_learning_curve.png) ??? --- # Lasso Regression `$$ \min_{w \in \mathbb{R}^p} \sum_{i=1}^n ||w^T\mathbf{x}_i - y_i||^2 + \alpha ||w||_1 $$` - Shrinks w towards zero like Ridge - Sets some w exactly to zero - automatic feature selection! ??? --- # Understanding L1 and L2 Penalties .wide-left-column[ ![:scale 100%](images/l2_l1_l0.png) ] .narrow-right-column[ .smaller[ `$$ \ell_2(w) = \sum_i \sqrt{w_i ^ 2}$$` `$$ \ell_1(w) = \sum_i |w_i|$$` `$$ \ell_0(w) = \sum_i 1_{w_i != 0}$$` ]] ??? --- # Understanding L1 and L2 Penalties .wide-left-column[ ![:scale 100%](images/l1_kink.png) ] .narrow-right-column[ .padding-top[ .smaller[ `$ f(x) = (2 x - 1)^2 $` `$ f(x) + L2 = (2 x - 1)^2 + \alpha x^2$` `$ f(x) + L1= (2 x - 1)^2 + \alpha |x|$` ]]] ??? --- class: center # Understanding L1 and L2 Penalties ![:scale 70%](images/l1l2ball.png) ??? --- class: center # Understanding L1 and L2 Penalties ![:scale 70%](images/l1l2ball_intersect.png) ??? --- # Grid-Search for Lasso ```python param_grid = {'alpha': np.logspace(-3, 0, 13)} print(param_grid) ``` ``` {'alpha': array([ 0.001, 0.003, 0.01, 0.032, 0.1, 0.316, 1., 3.162, 10., 31.623, 100., 316.228, 1000.])} ``` ```python grid = GridSearchCV(Lasso(normalize=True), param_grid, cv=10) grid.fit(X_train, y_train) print(grid.best_params_) print(grid.best_score_) ``` ``` {'alpha': 0.001} 0.837 ``` ??? --- ![:scale 90%](images/lasso_alpha_search.png) ??? --- .center[ ![:scale 60%](images/lasso_coefficients.png) ] ```python print(X_poly.shape) np.sum(lasso.coef_ != 0) ``` ``` (506, 104) 64 ``` ??? --- .smaller[ ```python from sklearn.linear_model import lars_path # lars_path computes the exact regularization path which is piecewise linear. X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42) alphas, active, coefs = lars_path(X_train, y_train, eps=0.00001, method="lasso") plt.plot(alphas, coefs.T, alpha=.5) plt.xscale("log") ``` ] .center[ ![:scale 55%](images/lars_path.png) ] ??? --- # Elastic Net - Combines benefits of Ridge and Lasso - two parameters to tune. `$$\min_{w \in \mathbb{R}^p} \sum_{i=1}^n ||w^T\mathbf{x}_i - y_i||^2 + \alpha_1 ||w||_1 + \alpha_2 ||w||^2_2 $$` ??? --- class: center # Comparing unit balls ![:scale 70%](images/l1l2_elasticnet.png) ??? --- # Parametrization in scikit-learn `$$\min_{w \in \mathbb{R}^p} \sum_{i=1}^n ||w^T\mathbf{x}_i - y_i||^2 + \alpha \eta ||w||_1 + \alpha (1 - \eta) ||w||^2_2 $$` Where $\eta$ is the relative amount of l1 penalty (`l1_ratio` in the code). ??? --- # Grid-searching ElasticNet ```python from sklearn.linear_model import ElasticNet param_grid = {'alpha': np.logspace(-4, -1, 10), 'l1_ratio': [0.01, .1, .5, .9, .98, 1]} grid = GridSearchCV(ElasticNet(), param_grid, cv=10) grid.fit(X_train, y_train) print(grid.best_params_) print(grid.best_score_) ``` ``` {'alpha': 0.0001, 'l1_ratio': 0.01} 0.718 ``` --- class: smaller # Analyzing grid-search results ```python import pandas as pd res = pd.pivot_table(pd.DataFrame(grid.cv_results_), values='mean_test_score', index='param_alpha', columns='param_l1_ratio') ``` .center[ ![:scale 60%](images/elasticnet_search.png) ] --- # Robust Regression ![:scale 85%](images/robust_regression.png) ??? --- # Least Squares Fit to Outlier Data ![:scale 80%](images/outliers_least_squares.png) ??? --- # Robust Fit ![:scale 80%](images/outliers_robust_fit.png) ??? --- class: smaller # Huber loss .padding-top[ .left-column[ ![:scale 100%](images/huber_loss.png) ] .right-column[ `$$min_{w, \sigma} \sum_{i=1}^n \left (\sigma + H\left ( \frac{X_iw - y_i}{\sigma}\right) \sigma \right ) + \alpha ||w||_2^2$$` `$$H(z) = \begin{cases} z^2, &if |z| < \epsilon, \\ 2\epsilon|z| & else\end{cases}$$` ] ] ??? --- # RANSAC ![:scale 80%](images/ransac_algorithm.png) ??? --- class: middle ![:scale 100%](images/ransac_algorithm2.png) ??? Here we can see the points that are determined inliers based on the fit. Clearly the blue one has the most inliers, so it is slected as solution. --- ??? --- class: middle # Questions ?


The chart below shows the credentials of all the users in our system. To change a user's credentials, drag and drop the user into the right box.


--- layout: page title: Opportunities date: 2013-02-18 17:26:16.000000000 -05:00 type: page published: true status: publish categories: [] tags: [] meta: _edit_last: '1' _wp_page_template: full-width-page.php _post_lock_status: unlocked _responsive_layout: default author: login: kenny email<EMAIL_ADDRESS>display_name: kenny first_name: Kenneth last_name: Flynn ---
We invite applications for Ph.D students interested in projects at the intersection of microbial ecology, evolution, genetics, genomics, and physiology. We find that students with experience in evolutionary biology and microbiology get off to a great start; those who are good geneticists or microbiologists but not familiar with evolution face some hurdles, but certainly not insurmountable.
We also invite applications for highly qualified postdoctoral scholars to study evolution-in-action, both in the lab and during infections, using population sequencing and microbial ecology and genetics. These positions are supported by awards from NIH and NASA but we will support applications by the fellow for independent research funding.
We are currently searching for a Senior Research Technician. This job description is posted here.
We always have several undergraduates and sometimes high school interns in the laboratory, but admission is competitive and requires a fit with my graduate students and technicians who might mentor them. Prospective undergraduate researchers, please familiarize yourself with our research before inquiring. I apologize if I can't always reply to all inquiries.
Thank you very much for your interest.
Vaughn


Flowsheet
This flowsheet Example is extracted from the Process Flowsheeting - A. Westerberg, H. Hutchison, R. Motard, P. Winter - Cambridge University Press - 1979.
The propylene feed is 2 mole % propane. In the
reactor the propylene is being converted at 20 bar and 200°C to
2-hexene by the reaction :
2C3H6 --> C6H12
Conversion of 80% of the propylene is anticipated. The flash separator recovers unreacted propylene and much of the propane, which acts as an inert substance here. The bleed is to prevent too high a build-up of propane.
C


This page requires Greasemonkey and a user script to do the searching web requests. This is normally blocked because of the security concerns it can bring up.
If after installing the user script it still cannot be detected, try refreshing the page or checking if the user script has been disabled.


By Art Agnos
When I became mayor in 1988, existing government policy for homelessness consisted of the “American disaster model” employed in natural disasters like floods and tornadoes. Cities opened armories and served coffee and doughnuts in what was expected to be temporary relief. Afterward, the homeless “victims” would resume their lives.
My administration recognized that the homelessness created by disasters like drug abuse, mental illness, domestic violence, alcoholism, runaway children, unemployment or low wages required a different approach than homelessness created by floods and hurricanes.
In 1989, San Francisco homeless advocates, religious leaders, nonprofit and social service staff gathered to invent a first-of-a-kind plan. That plan, “Beyond Shelter,” is a solution but not a fast solution — there are no fast solutions. Sadly, we, the politicians and the public, have lacked the conviction and commitment to realize success in solving homelessness.
“Beyond Shelter” was developed to deal with the aftershocks of national political and economic decisions that put hundreds of homeless people on city streets.
The Reagan administration had cut the U.S. Department of Housing and Urban Development’s budget from $32 billion to $8 billion for affordable housing — as well as minimum financial assistance such as Supplemental Security Income. The combined effect was terrible.
Then, just as “Beyond Shelter” got under way, the Loma Prieta earthquake hit on Oct. 17, 1989, and the city faced a new homeless crisis.
Devastation in the Marina neighborhood suddenly forced residents from their homes. Emergency shelter and services were quickly put in place by national agencies. Not as much attention was paid to more than a thousand formerly homeless people living in the South of Market single-room-occupancy hotels made homeless again. The Red Cross and Federal Emergency Management Agency offered immediate housing aid to homeowners and renters, but denied the same housing aid to those who had been living on public assistance in SRO hotels.
I demanded, received and shared with other badly damaged cities, donated earthquake funds totaling more than $30 million, which was surreptitiously taken from the city by the Red Cross and deposited in its Washington, D.C., accounts.
“Beyond Shelter” was inaugurated with San Francisco’s share with the opening of two centers totaling 480 beds. These facilities initially were modeled after the magnificent Delancey Street Foundation, a successful program that never compromises with the highest standards of quality and design.
The homeless in the Civic Center encampment, which I had allowed to exist in the months between the earthquake and the opening of the centers nine months later, were peacefully moved to the multiservice centers with priority for placement in the new “Beyond Shelter” programs.
At the multiservice centers, social service and health professionals would evaluate each new arrival to determine what services he or she needed to recover a productive life. Compassion and aggressiveness were balanced in a case management system designed to help homeless people recover by, first, housing them and then linking them with appropriate services.
“Beyond Shelter” had three levels of service:
MultiService Centers (think today’s Navigation Centers) accepted individuals and families — with pets — for a diagnostic stay to identify the conditions responsible for their homeless “disaster.”
A part of this was the McMillan Emergency Drop-in Center, where individuals could crash — with no questions asked or be brought there in “Mobile Assistance Patrol” vans, always on standby for that purpose.
Once they were diagnosed, the homeless entered the appropriate transitional housing with supportive services matching their evaluation. Some might need a short stay — others a longer one.
Permanent housing — the ultimate goal of the program.
“Beyond Shelter” had two essential assets:
— A Community Housing Partnership to develop, maintain and employ homeless people in their housing. Today, this agency houses and supports more than 1,000 formerly homeless people. Jeff Kositsky, former director of Community Housing Partnership, was just named as the leader of the new San Francisco Department of Homelessness and Supportive Housing.
— A “modified payment” program to stabilize existing SRO housing by guaranteeing rent payments to landlords in exchange for rent discounts. This helped secure the existing housing stock as well as complement the longer-term commitment to nonprofit housing development.
The final, and more controversial, element called for severely troubled homeless individuals who acted out in socially unacceptable or uncivilized ways to be sent by court order to a “rehabilitation farm” for treatment.
The cost estimates to build out “Beyond Shelter” were about $125 million in today’s dollars for a target population of 6,000. It certainly fit within the current budget spending of $245 million.
Nevertheless, we knew that San Francisco needed the buy-in of the Bay Area cities. In May 1990, mayors from San Jose, Oakland, Berkeley, Richmond and San Francisco signed a joint action plan and encouraged every city around the bay to join the effort.
By 1991, we had added 444 beds in transitional housing, and awarded funding to construct 645 more for a total of 1,500 new places.
So why didn’t this state-of-the-art plan work?
The monumental human tragedy that is homelessness cannot be solved by constantly changing plans at election day. Elected officials must be willing to assume immediate political risks in order to achieve a long-term solution. Further, the public must accept responsibility for its fair share of the solution.
NIMBYism threatened any effort to locate a necessary component of a homeless plan anywhere except the Tenderloin. People want the issue to be solved, but not at their inconvenience. But it can be done — just look at the magnificent Delancey Street facilities located in Pacific Heights and now along the high-end waterfront.
The media has the responsibility to do more than the occasional special feature. Recently, homelessness came into the news because of the tent crisis on Division Street. This teachable moment must be continued regularly to inform the community about honest, workable solutions.
No plan will succeed until we demonstrate that we have the commitment to do all that is necessary to make an effective plan work for the most unpopular group of needy Americans.


It is low on dependencies an can be easily installed with composer on other projects.
All the ideas behind the packages are represented in interfaces. You can implement what's missing.
Created with packages that can be used separately. If you need a dependency container just use Slick\Di


| HTML::Element::traverse - discussion of HTML::Element's traverse method |
HTML::Element::traverse - discussion of HTML::Element's traverse method
This document describes version 5.03 of HTML::Element::traverse, released September 22, 2012 as part of HTML-Tree.
# $element->traverse is unnecessary and obscure. # Don't use it in new code.
HTML::Element
provides a method traverse
that traverses the tree
and calls user-specified callbacks for each node, in pre- or
post-order. However, use of the method is quite superfluous: if you
want to recursively visit every node in the tree, it's almost always
simpler to write a subroutine does just that, than it is to bundle up
the pre- and/or post-order code in callbacks for the traverse
method.
Suppose you want to traverse at/under a node $tree and give elements an 'id' attribute unless they already have one.
You can use the traverse
method:
{ my $counter = 'x0000'; $start_node->traverse( [ # Callbacks; # pre-order callback: sub { my $x = $_[0]; $x->attr('id', $counter++) unless defined $x->attr('id'); return HTML::Element::OK; # keep traversing }, # post-order callback: undef ], 1, # don't call the callbacks for text nodes ); }
or you can just be simple and clear (and not have to understand the
calling format for traverse
) by writing a sub that traverses the
tree by just calling itself:
{ my $counter = 'x0000'; sub give_id { my $x = $_[0]; $x->attr('id', $counter++) unless defined $x->attr('id'); foreach my $c ($x->content_list) { give_id($c) if ref $c; # ignore text nodes } }; give_id($start_node); }
See, isn't that nice and clear?
But, if you really need to know:
The traverse()
method is a general object-method for traversing a
tree or subtree and calling user-specified callbacks. It accepts the
following syntaxes:
These all mean to traverse the element and all of its children. That is, this method starts at node $h, "pre-order visits" $h, traverses its children, and then will "post-order visit" $h. "Visiting" means that the callback routine is called, with these arguments:
$_[0] : the node (element or text segment), $_[1] : a startflag, and $_[2] : the depth
If the $ignore_text parameter is given and true, then the pre-order call will not be happen for text content.
The startflag is 1 when we enter a node (i.e., in pre-order calls) and 0 when we leave the node (in post-order calls).
Note, however, that post-order calls don't happen for nodes that are text segments or are elements that are prototypically empty (like "br", "hr", etc.).
If we visit text nodes (i.e., unless $ignore_text is given and true), then when text nodes are visited, we will also pass two extra arguments to the callback:
$_[3] : the element that's the parent of this text node $_[4] : the index of this text node in its parent's content list
Note that you can specify that the pre-order routine can be a different routine from the post-order one:
$h->traverse( [\&pre_callback,\&post_callback], ...);
You can also specify that no post-order calls are to be made, by providing a false value as the post-order routine:
$h->traverse([ \&pre_callback,0 ], ...);
And similarly for suppressing pre-order callbacks:
$h->traverse([ 0,\&post_callback ], ...);
Note that these two syntaxes specify the same operation:
$h->traverse([\&foo,\&foo], ...); $h->traverse( \&foo , ...);
The return values from calls to your pre- or post-order routines are significant, and are used to control recursion into the tree.
These are the values you can return, listed in descending order of my estimation of their usefulness:
...to keep on traversing.
Note that HTML::Element::OK
et
al are constants. So if you're running under use strict
(as I hope you are), and you say:
return HTML::Element::PRUEN
the compiler will flag this as an error (an unallowable
bareword, specifically), whereas if you spell PRUNE correctly,
the compiler will not complain.
...to block traversing under the current element's content.
(This is ignored if received from a post-order callback,
since by then the recursion has already happened.)
If this is returned by a pre-order callback, no
post-order callback for the current node will happen.
(Recall that if your callback exits with just return;
,
it is returning undef -- at least in scalar context, and
traverse
always calls your callbacks in scalar context.)
...to abort the whole traversal immediately. This is often useful when you're looking for just the first node in the tree that meets some criterion of yours.
...to abort continued traversal into this node and its parent node. No post-order callback for the current or parent node will happen.
Like PRUNE, except that the post-order call for the current node is not blocked.
Almost every task to do with extracting information from a tree can be
expressed in terms of traverse operations (usually in only one pass,
and usually paying attention to only pre-order, or to only
post-order), or operations based on traversing. (In fact, many of the
other methods in this class are basically calls to traverse()
with
particular arguments.)
The source code for HTML::Element and HTML::TreeBuilder contain several examples of the use of the "traverse" method to gather information about the content of trees and subtrees.
(Note: you should not change the structure of a tree while you are traversing it.)
[End of documentation for the traverse()
method]
Now, if you've been reading Structure and Interpretation of Computer Programs too much, maybe you even want a recursive lambda. Go ahead:
{ my $counter = 'x0000'; my $give_id; $give_id = sub { my $x = $_[0]; $x->attr('id', $counter++) unless defined $x->attr('id'); foreach my $c ($x->content_list) { $give_id->($c) if ref $c; # ignore text nodes } }; $give_id->($start_node); undef $give_id; }
It's a bit nutty, and it's still more concise than a call to the
traverse
method!
It is left as an exercise to the reader to figure out how to do the
same thing without using a $give_id
symbol at all.
It is also left as an exercise to the reader to figure out why I
undefine $give_id
, above; and why I could achieved the same effect
with any of:
$give_id = 'I like pie!'; # or... $give_id = []; # or even; $give_id = sub { print "Mmmm pie!\n" };
But not:
$give_id = sub { print "I'm $give_id and I like pie!\n" }; # nor... $give_id = \$give_id; # nor... $give_id = { 'pie' => \$give_id, 'mode' => 'a la' };
Note that you may at times see an iterative implementation of pre-order traversal, like so:
{ my @to_do = ($tree); # start-node while(@to_do) { my $this = shift @to_do;
# "Visit" the node: $this->attr('id', $counter++) unless defined $this->attr('id');
unshift @to_do, grep ref $_, $this->content_list; # Put children on the stack -- they'll be visited next } }
This can under certain circumstances be more efficient than just a
normal recursive routine, but at the cost of being rather obscure. It
gains efficiency by avoiding the overhead of function-calling, but
since there are several method dispatches however you do it (to
attr
and content_list
), the overhead for a simple function call
is insignificant.
The traverse
method does have the fairly neat features of
the ABORT
, PRUNE_UP
and PRUNE_SOFTLY
signals. None of these
can be implemented totally straightforwardly with recursive
routines, but it is quite possible. ABORT
-like behavior can be
implemented either with using non-local returning with eval
/die
:
my $died_on; # if you need to know where... sub thing { ... visits $_[0]... ... maybe set $died_on to $_[0] and die "ABORT_TRAV" ... ... else call thing($child) for each child... ...any post-order visiting $_[0]... } eval { thing($node) }; if($@) { if($@ =~ m<^ABORT_TRAV>) { ...it died (aborted) on $died_on... } else { die $@; # some REAL error happened } }
or you can just do it with flags:
my($abort_flag, $died_on); sub thing { ... visits $_[0]... ... maybe set $abort_flag = 1; $died_on = $_[0]; return; foreach my $c ($_[0]->content_list) { thing($c); return if $abort_flag; } ...any post-order visiting $_[0]... return; }
$abort_flag = $died_on = undef; thing($node); ...if defined $abort_flag, it died on $died_on
Current maintainers:
Original HTML-Tree author:
Former maintainers:
You can follow or contribute to HTML-Tree's development at http://github.com/madsen/HTML-Tree.
Copyright 2000,2001 Sean M. Burke
| HTML::Element::traverse - discussion of HTML::Element's traverse method |


Issue Tracker
H.M. Solutions 2917.
Add New Issue
Description
Severity
Low
Medium
High
Assigned To
Add