Copyright 2002-2006 by The BioBike Team (contact<EMAIL_ADDRESS>First, let's make a pretty long list of the letters of the alphabet.
>> (setf letters '(a b c d e f g h i j k l m n o p q r s t u v w x y z))Recall that each letter (each "element") in the above is a symbol; we could just as well have given them longer names:
>> (setf letters '(a bee see dee eee elephant gee! ach eye jay kay eel emu en oh! >> pee que are es tea ewe vee double-ewe ex why? zeeeeeeee))In fact, I like that one better, lets use that one!
So get an element from a list (or any sequence), use ELT:
>> (elt letters 1) :: BEE ; Remember that the first (a) is position 0, not 1! >> (elt letters 11) :: EELGetters (accessors) usually have "setters" that change the thing you got.  ACH EYE JAY KAY (AN EEL IS NOT A SNAKE) EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE)It's extremely important to deeply understand this example! (You're asking: What's so deep about it?!)
First, notice that the arguments to SETF are the accessor (i.e., (elt letters 11) in this case) and the new value (the list: (an eel is not a snake)). This is the way pretty much all data structure changing works: You tell lisp how to reach into the data structure, and then what to put there in place of whatever used to be there. (The sharp-of-eye will notice that the way we set the value of LETTERS to begin with was just the same!)
Second, notice that we replaced a symbol by a whole list. The elements of lists can be anything you like (symbols, lists, lists of lists, and anything else in Lisp!). This makes lists extremely useful data structures! So useful, in fact, that Lisp is named after them! ("Lisp" stands for "List Processing Language"!)
Third, notice in passing that we had to quote the new list (i.e., '(an eel is not a snake), not just (an eel is not a snake)). Why? [Hint: Remember the recursive evaluation procedure from moons ago!]
Fourth, and most importantly, SETF destructively changed our list! That is, it smashed the new element (the list: (an eel is not a snake)) in place of the old element (the symbol: eel). This change is permanent, and is a very easy way to confuse yourself.
Watch:
;;; Let's get back to where we were: >> (setf letters '(a bee see dee eee elephant gee! ach eye jay kay eel emu en oh! >> pee que are es tea ewe vee double-ewe ex why? zeeeeeeee)) :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Now let's set aside our letters for safe keeping: >> (setf hold-letters letters) :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Now we'll change the original list (same as we did above): >> (setf (elt letters 11) '(an eel is not a snake)) :: (AN EEL IS NOT A SNAKE) >> letters :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY (AN EEL IS NOT A SNAKE) EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Looks good. Thank goodness we have hold-letters in case we need the ;;; original list: >> hold-letters :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY (AN EEL IS NOT A SNAKE) EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Oops!!! What's happened?!!!What happened indeed? When we SETF'ed HOLD-LETTERS to LETTERS, all that it did was to make HOLD-LETTERS be the very same list as LETTERS. The don't just look alike -- that are the very same list! Anything that changes the one, also changes the other! See, I warned you that you'd be confused. But this confusion is the way to Lisp enlightenment!
One way to think about this (in fact, the correct way), is to think of it in terms of pointers, sort of like arrows that point from one thing to another. SETF changes where arrows point. When we SETF'ed LETTERS originally, all we did was to put a pointer (an arrow) from the name LETTERS to the list (A BEE ...). Each ELT of that list is actually another pointer, in the initial case from the place in the list to the symbols: A, BEE, etc. When we SETF'ed the (ELT LETTERS 11) to (AN EEL IS NOT A SNAKE), all we did was change the pointer at the 11 position of our list away from the symbol EEL, and toward the new list: (AN EEL IS NOT A SNAKE). So far so good, but how does that help us understand that confusing mess where LETTER and HOLD-LETTERS seem to point to the very same list? ... wait a minute! We just answered our own question: When we SETF'ed HOLD-LETTERS to LETTERS all that did was to put an arrow (a pointer) from the symbol HOLD-LETTERS to the very same list as LETTERS was pointing to. There was only ever one list that both LETTERS and HOLD-LETTERS were both pointing to! So when we changed the pointer in the list of letters from EEL to point to (AN EEL IS NOT A SNAKE), both LETTERS and HOLD-LETTERS got changed!
Wow! That's a brain-full! Don't worry if you don't fully understand this; You'll see it again and again. Just be aware that when you SETF things, you're changing them, and that there could be someone else (even you) that depends upon their value being stable!
Of course, Lisp provides a way around this problem. Here's what we meant to do:
;;; Let's get back to where we were: >> (setf letters '(a bee see dee eee elephant gee! ach eye jay kay eel emu en oh! >> pee que are es tea ewe vee double-ewe ex why? zeeeeeeee)) :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Now let's set aside our letters for safe keeping: >> (setf hold-letters (copy-seq letters)) :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Now we'll change the original list (same as we did above): >> (setf (elt letters 11) '(an eel is not a snake)) :: (AN EEL IS NOT A SNAKE) >> letters :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY (AN EEL IS NOT A SNAKE) EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Looks good. Thank goodness we have hold-letters in case we need the ;;; original list: >> hold-letters :: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE) ;;; Ahhhhhhhhh. Much better!COPY-SEQ (in red) made a COPY of the list (A BEE ...) and then we pointed HOLD-LETTERS to that copy instead of to the original list.
Are you enlightened?
Okay, well enough of that. Let's iterate!
Let's do something very slightly more interesting:
Here's something slightly more intersting:
Some more XLooping for fun and profit (well, okay, just fun):
Watch:
Here's another:
You can loop over strings too, but be aware that you're going to get
weird looking characters (with #\...) because what you're looping
over is the individual characters:
Let's combine xloop and subseq, and see another form of loop while we're at it:
Let's move on to somewhat more interesting things.
That's a list of frames each of which represents a
gene. (Hopefully you recall frames from the tour. A frame is a unit of
knowledge. We'll work a lot more with frames as we get into more
biological examples.)
There's a BioLisp function called EXTRACT-SEQUENCE that gets the gene
sequence given a gene frame, watch:
That's just a string. So we have a list of genes, and can get the
strings that represent their sequences out of them using
EXTRACT-SEQUENCE. Let's do something simple with loops on
these. Suppose that we wanted to get a list of the first 100 nucleotides from
each of these genes. How about:
A very common thing to want to do is to read and write files. There are
some arcane but standard ways to do this using XLoops. In biology the
common standard for sequence storage is the "FASTA" file. Fasta files
always look like this:
BioLisp has built-in facilities to deal with FASTA files very
efficiently, but we're going to do our own FASTA processing as an
exercise in looping. Let's start by writing out those Carboxy Lyase
genes to a fasta file. To do this we open the file, write each one
with a defline. Easy:
The WITH-OPEN-FILE is a little complex, although most of the keywords
are obvious. The only non-obvious part is "ostream". That's just the
name of the variable that WITH-OPEN-FILE connects the file to so that
you can write to it, which we did using the format functions in the
body of the loop. Notice that you don't have to close the file, when
the WITH-OPEN-FILE ends (that is, at the end of its matching
close-paren) the file gets closed automatically. (Or, as they say:
"automagically" :-)
The next slightly weird thing is the #^FNAME -- you might recall from
the lesson on frames that that's just the name of the frame -- in this
case, the name of the gene.
Okay, good, so now lets read the files back in, and, just to test it,
collect the lengths of the genes in the file:
for line = ... : Instead of "in" we
used "=" -- this means that each time through the loop a new value is
calculated for LINE. 'In' is only used when we are iterating over a
pre-computed structure, but here we want it to go out to the file each
time and read the next line.
(read-line istream nil nil) : This reads a line from istream,
and returns NIL when it hits the end of the file. This goes with the
next line: until (null line). So, the loop will continue until
we hit the end, at which point READ-LINE will return NIL to LINE, and
the UNTIL (NULL LINE) clause will stop the loop!
... collect (list line (length (read-line istream))) : We're
depending here upon the fact that each fasta entry is exactly two
lines: the defline and one line of sequence information. We know that
that's the case because we wrote this file out!!
This code would definitely not work if we tried to read a
standard FASTA, which has multiple lines. That's a little trickier
because you don't know when you've hit the end of an entry until you
see either the next defline, or the end of the file. We won't try to
that that at the moment, although it's instructive to try to figure
it out.
Let's do the slightly simpler thing first of putting out 50 characters
at a time, instead of writing the whole thing out as one long line. To
do that we want the same code as above, but when it prints the
sequence, we put out only 50 characters at a time, like this:
Okay, enough of that nonsense, let's get back to more interesting
problems.
Here's another example, again using ELT, which is also how you get a
single element from an array, like a string::
This will put an empty hash table into the variable (in this case:
MY-TABLE). You'll see something like this:
The way that you put things into a hash table, and the way that you
get them out is just like you would for any other data structure,
using SETF on the accessor form. The accessor form for a hash
table look like this:
And to look up my phone number:
Let's clear that entry out:
Okay, so let's do an experiment with our Carboxy Lyase genes (which we
have, as you might recall, in the variable: cxl-genes). Let's
associate each of those with its length. That's sort of a boring
association because we can just compute it easily using (length ...),
but it's just a demo, so bear with me here:
Recall that I said that you can associate anything with anything in a
hash-table. Let's do something a little more interesting. Suppose
that we want to know which genes among our carbox lyases genes have a
particular nucleotide motif. In fact, we want to know, for some
specific nucleotide motif, which genes contain that version of
the motif. The motif I have in mind is five-nt long, and they're all
Ts except the middle one, which can be any nt (A T G or C).
We can find one string in another by the SEARCH function:
We're going to use one new construction. Above we used SETF with the
GETHASH accessor to change the table value, here we're going to use
PUSH to add to the head of the list being built up in the table
key. You'll see what we mean. Watch:
Let's create a function, called XAA-LENGTH, that figures out the
length of the Amino Acid translation of a given gene, given its
frame. We want to add a few options to the call of
TRANSLATE-D/RNA-TO-AA that will help in possible problem cases. (If
you do: (HELP TRANSLATE-D/RNA-TO-AA) these are explained.)
The main thing to notice about all the above is that there are
several ways to do the same job.
Here's an example that demonstrates the difference between the loop keywords
AS and WITH.
Watch this, this is sort of fancy. Let's take the output of the
previous loop:
If the elements we are iterating over are lists (in this case lists of
two elements each) we can tell XLOOP to bind different variables to
each part subpart of each sublist as the iteration proceeds. (This
destructuring may be arbitrarily complex.)
Here's a very complex example that counts up the number of genes in
each chromosome (or plasmid -- i.e., each contigous sequence) of an
organism. We're going to create a list of pairs (called
contig-genes-list) that looks like: (... (contig count) ...). it
starts out as the count of 0, as: (... (contig 0) ...). (Note how this
is embedded in the LET binding part!) Then we run through all the
genes and increment the count (the second element of each sublist in
CONTIG-GENES-LIST) for the contig that each gene is found on.
Finally, we print the results. Note the destructuring here CONTIG and
GENE-COUNT get bound to the first and second of each element in the
contig-genes-list!)
Here's an illustration of the BY feature of LOOP, used by on numbers
and lists:
There are some very confusing things that are worth knowing about
strings. You don't have to study this section now, but you should be
aware that it's here; Maybe skim it once without trying to understand
it deeply, so that when you run into these you'll say to yourself:
"Oh, yeah, there was that optional section on totally confusing things
about strings, maybe I should go back and look at that again in more
detail." It probably won't help, but on the off chance that it will,
here we go anyhow.
Above we saw one sort of confusing thing about strings: They are made
up of characters. Okay, that sounds like, sort of "Duh!", but the
characters print out in this funky way with #\ before them. You can
actually type a single character by typing, for example for the
character 'c': #\c
Here's a list of several characters:
Okay, with all that in mind, on to the confusing part:
The backslash is Lisp's escape character. That is, if you want to put
a double quote into a string, you can't just type: "this string has a
" in it" because the quote in the middle will terminate the string and
totally confuse Lisp (not to mention you and me!) So you have to
type: "this string has a \" in it"
(Note that in typing strings you don't have to type the # ... that's
just to denote a single character as its own value. You use the '#\'
notation to represent characters OUTSIDE of strings. The #\ notation
is not recognized INSIDE of double quotes. So "#\a" is a string
consisting of two character, pound sign and the letter 'a'. Whereas
#\a is the single character object, the letter a. )
You can quote any character, so the string: "abc" has exactly the same
characters as the string: "\a\b\c". So if you have a string with a
double quote in it, as above, you have to type it in with a \ and
it'll appear with a \ when it's printed out:
Now, what if you waht to put a backslash INTO a string? To put a
backslash in a string you have to escape the escape character:
Don't believe me?
Copyright 2002-2006 by The BioBike Team (contact<EMAIL_ADDRESS>Looping in Lists
The simplest way to iterate over a list is with a construct call
XLOOP. Here are some examples:
;;; Let's get our letters back:
>> (setf letters '(a bee see dee eee elephant gee! ach eye jay kay eel emu en oh!
>> pee que are es tea ewe vee double-ewe ex why? zeeeeeeee))
:: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE
ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE)
>> (xloop for letter in letters
>> do (print letter))
::
A
BEE
SEE
DEE
EEE
ELEPHANT
GEE!
...etc...
> NIL
Hard to get much simpler than that! Notice that this loop prints out
things, but doesn't actually return anything (the NIL at the end is
the result). We can get loop to return things for us quite easily:
>> (xloop for symbol in letters
>> collect symbol)
:: (A BEE SEE DEE EEE ELEPHANT GEE! ACH EYE JAY KAY EEL EMU EN OH! PEE QUE ARE
ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE)
COLLECT says to give me back a new list composed of whatever got
computed in the loop. The above example seems boring -- it just gave
us back the same list. (Actually, it gave us a copy of the list
... in fact, the above XLoop is the definition of COPY-SEQ!)
>> (xloop for mylet in letters
>> collect (list mylet mylet))
:: ((A A) (BEE BEE) (SEE SEE) (DEE DEE) (EEE EEE) (ELEPHANT ELEPHANT) (GEE! GEE!)
(ACH ACH) (EYE EYE) (JAY JAY) (KAY KAY) (EEL EEL) (EMU EMU) (EN EN)
(OH! OH!) (PEE PEE) (QUE QUE) (ARE ARE) (ES ES) (TEA TEA) (EWE EWE)
(VEE VEE) (DOUBLE-EWE DOUBLE-EWE) (EX EX) (WHY? WHY?)
(ZEEEEEEEE ZEEEEEEEE))
Not that much more intersting, but anyway notice that I keep using a
different name for LETTER, SYMBOL, MYLET -- this is the variable that
will get "bound" to each element of the list. What we call this
doesn't matter -- it can be any symbol, so I'll change it a lot here
so that you get used to it being any symbol at all.
>> (xloop for maybe-an-animal? in letters
>> when (member maybe-an-animal? '(bee eel ewe dog cat emu mouse elephant))
>> collect maybe-an-animal?)
:: (BEE ELEPHANT EEL EMU EWE)
Okay, it's not that interesting, but we did get to learn two new
things: the WHEN clause in XLoop, and the Lisp MEMBER function. The
WHEN clause will work with anything that computes a Lisp truth value
(that is, NIL versus anything except NIL). In fact, watch what member
returns:
>> (member 'emu letters)
:: (EMU EN OH! PEE QUE ARE ES TEA EWE VEE DOUBLE-EWE EX WHY? ZEEEEEEEE)
>> (member 'dog letters)
:: NIL
MEMBER actually gives you the whole list including and after the
member you're looking for, and NIL if it can't find the desired
member.
>> (xloop for a-number from 1 to 1000
>> as root = (sqrt a-number)
>> when (= (round root) root)
>> collect a-number)
:: (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 ...)
Here AS clause computes the square root of A-NUMBER each time through,
and then the WHEN clause uses ROOT, thus computed, to decide if
A-NUMBER is a perfect square or not.
Strings
Remember from previous lessons that strings are any sequence of
characters surrounded by double-quotes. Just like lists, you can take
the elements of string. Each element of a string is a single
character.
>> (setf a-string "this is a string")
:: "this is a string"
>> (elt a-string 3)
:: #\s
The ugly #\s thing is a character "s". The
reasons for the ugly #\ notation is so that the character #\a, for
example, isn't confused with the symbol a or the string of only one
character long "a".
>> (elt a-string 4)
:: #\space
The character representation of a space is written out: #\space; most
other characters are just their own name (like s was #\s). This
sounds confusing (and it is), but it's important to understand that a
string (even a one letter long string) is a sequence of characters.
>> (xloop for each-single-char in "this is a string"
>> collect each-single-char)
:: (#\t #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\s #\t #\r #\i
#\n #\g)
In an optional lesson near the end of this tutorial we talk a little
more about strings and characters.
Other Sequence Gizmos
As we said above, both lists and strings (and a few other things) are
examples of sequences. Generally speaking, what you iterate (loop)
over are sequences. There are bunches of functions that operate on
sequences. The most useful one is xloop, as we've just seen. Another
very useful one is SUBSEQ, which gets a subsequence of a given
sequence:
>> (setq spanish-planes "the planes in spain fall mainly in the rain")
>> (subseq spanish-planes 0 19)
:: "the planes in spain"
>> (subseq spanish-planes 19)
:: " fall mainly in the rain"
>> (subseq spanish-planes 20 24)
:: "fall"
>> (subseq letters 10 20)
:: (KAY EEL EMU EN OH! PEE QUE ARE ES TEA)
(Recall that the first element of a sequence is the 0th, and the
second the 1th, etc.)
>> (xloop for start from 1 to 20
>> for end from 15 to 25
>> collect (subseq spanish-planes start end))
:: ("he planes in s" "e planes in sp" " planes in spa" "planes in spai"
"lanes in spain" "anes in spain " "nes in spain f" "es in spain fa"
"s in spain fal" " in spain fall" "in spain fall ")
That time we used two different iteration variables: START and END
(which we could have just as well called anything we liked, like TRATS
and DNE for all that loop cares!); Each time through the loop
both of these were updated. So we should have always got
elements of length 14 (15 -- the distance between our iterators, minus
1). Let's check:
>> (xloop for result in (xloop for start from 1 to 20
>> for end from 15 to 25
>> collect (subseq spanish-planes start end))
>> collect (length result))
:: (14 14 14 14 14 14 14 14 14 14 14)
Looks right, but .... Whoa! what was all that about!? If
you look carefully at the above complex mess, all that I did was to
write a normal loop like this:
(xloop for result in SOMETHING
collect (length result))
which should be easy to understand. Then I replaced SOMETHING with:
(xloop for start from 1 to 20
for end from 15 to 25
collect (subseq spanish-planes start end))
just like above. Lisp is perfectly happy with this. It just evaluates
the subseq loop, just like we did above, getting: "he planes in s" "e
planes in sp" ... etc), and then passes that result to the length
loop. This style of programming is called "functional programming",
where you pass the result of one function as input to another, and
it's done a LOT in lisp (although usually not quite so spectacularly
without warning!)
Some Biological Iteration
We now have all the tools we need to do some work on gene
sequences. Let's start by getting a handful of genes; We'll pick up
the ones that happen to be annotated into the Gene Ontology as
producing Carboxy-Lyase proteins:
>> (setq cxl-genes (#^Go.Related-Genes #$GO.Carboxy-LyaseActivity))
::
(#$S6803.sll0578 #$S6803.slr0662 #$S6803.slr0546 #$S6803.sll0901
#$S6803.sll0504 #$S6803.slr0536 #$S6803.sll0892 #$S6803.sll0838
#$S6803.sll1641 #$S6803.slr1099 #$S6803.slr1312 #$A7120.all3569
#$A7120.alr2983 #$A7120.alr2945 #$A7120.all0395 #$Tery.Te?6781
#$Tery.Te?6780 #$Tery.Te?4796 #$Tery.Te?4797)
(This list might differ slightly when you do it because of changes in
the knowledge base since this lesson was written.)
>> (extract-sequence #$A7120.alr2945)
"ATGGTTTTGGTGGGCAATGCCCACCCTACAGATACTGAGAATTTTATACCTAATTACCTAACAAATAAAATGATT..."
;; >>> Line truncated to 80 (was 1503). Use SET-OUTPUT-LIMITS to adjust width
(Even though it tolds us that the printout was truncated, the whole
sequence is still there, it just refuses to print it all out because
it's so long!)
>> (xloop for gene in cxl-genes
>> collect (subseq (extract-sequence gene) 0 100))
::
("ATGGAAACAAAATTAACCACAGTGGGGGTAATTGGTGGTGGACAGTTGGCCTGGATGATGGCCCAGGAAGCCCCCCGATTGGGATTAAAACTTGCAGTGC"
"ATGGAAGGGCAGTCAATCGAACTAGAACTAAGTGTCATGGCAATGCCGGAGTTAATCGACAGTACTGAAGCAGGCCATACCGCCGGGGTGAAAACTGATT"
"ATGGAAATTCGCCGCCGGCCTCCTAACCCCCCCATCAAAGTTGACATTCTTCAGTATCAAATTAAGCATCCAGAAGCGGCTCCCCGTCACATTCTGGAGG"
"ATGACTTCCCCCTCTCCCCTGGTCGGCATCATCATGGGAAGCGATTCCGATCTCCCCACCATGGCAGCGGCGATCGCCGTCTGTGAAGAATTTGCCGTAC"
...etc...
That was easy! Let's do something more interesting.
>various information about the following sequence
ATGGAAACAAAATTAACCACAGTGGGGGTAATTGGTGGTGGACAGTTGGC
CTGGATGATGGCCCAGGAAGCCCCCCGATTGGGATTAAAACTTGCAGTGC
ATGGAAGGGCAGTCAATCGAACTAGAACTAAGTGTCATGGCAATGCCGGA
GTTAATCGACAGTACTGAAGCAGGCCATACCGCCGGGGTGAAAACTGATT
... etc ...
>next entry
... etc ...
The > line before each entry in called the "defline", and the sequence
information is usually, but not always, 50 characters long. FASTA is
used for LOTS of different sorts of things, often it's not even
sequence information, so the 50 character property is definitely
not a rule to depend upon.
>> (with-open-file (ostream "cxl.fasta" :direction :output :if-exists :supersede)
>> (xloop for gene in cxl-genes
>> as sequence = (extract-sequence gene)
>> (format ostream ">~a~%" (#^fname gene))
>> (format ostream "~a~%" sequence)))
;;; That's all there is to it! Let's see if it worked:
>> (list-file-contents "cxl.fasta")
----- cxl.fasta -----
>S6803.sll0578
ATGGAAACAAAATTAACCACAGTGGGGGTAATTGGTGGTGGACAGTTGGCCTGGATGATGGCCCAGGAAGCCCCCCGATTGGGATTAAAACTTGCAGTGCAAACCCCTGGGGAAAGTGATCCGGCCGTGGCATTGGCGGACAAAGTGGTATTGACGGCGATCGCCGATGGGGAAGGAACTAGGGAGTTAGCAGAGCA...
>S6803.slr0662
ATGGAAGGGCAGTCAATCGAACTAGAACTAAGTGTCATGGCAATGCCGGAGTTAATCGACAGTACTGAAGCAGGCCATACCGCCGGGGTGAAAACTGATTCCAATCCCCAGGCGATCGCCCAAGACCGTCGTTGGACCATTGACGACAGCGAAAACCTCTACCGCATCACTGGTTGGGGGGAACCTTACTTTTCCAT...
>S6803.slr0546
ATGGAAATTCGCCGCCGGCCTCCTAACCCCCCCATCAAAGTTGACATTCTTCAGTATCAAATTAAGCATCCAGAAGCGGCTCCCCGTCACATTCTGGAGGAAATTGTTTGGCATAAGGAAAAGGAAGTGGCCCAACGGCGAGAATTAGTCCCCCTGGTCAAACTCCAAAGTTTAGTCAAGGACATGACTCCCCCATT...
...etc...
Cool! Now, let's look at the way we did that in a little more detail.
>> (with-open-file (istream "cxl.fasta" :direction :input)
>> (xloop for line = (read-line istream nil nil)
>> until (null line)
>> collect (list line (length (read-line istream)))))
::
((">S6803.sll0578" 1167) (">S6803.slr0662" 2088) (">S6803.slr0546" 888)
(">S6803.sll0901" 531) (">S6803.sll0504" 1410) (">S6803.slr0536" 1053)
(">S6803.sll0892" 438) (">S6803.sll0838" 696) (">S6803.sll1641" 1404)
(">S6803.slr1099" 621) (">S6803.slr1312" 1980) (">A7120.all3569" 384)
(">A7120.alr2983" 717) (">A7120.alr2945" 1503) (">A7120.all0395" 1617)
(">Tery.Te?6781" 456) (">Tery.Te?6780" 444) (">Tery.Te?4796" 207)
(">Tery.Te?4797" 333))
Wow, great! A few new things to notice:
>>(with-open-file (ostream "cxl.fasta" :direction :output :if-exists :supersede)
>> (xloop for gene in cxl-genes
>> as sequence = (extract-sequence gene)
>> (format ostream ">~a~%" (#^fname gene))
>> (xloop for pos from 0 to (length sequence) by 50
>> (format ostream "~a~%"
>> (subseq sequence pos (+ 50 pos))))))
<<< Evaluation failed. Actual error: >>>
<<<
Within the loop "(LOOP FOR POS FROM 0 TO (LENGTH SEQUENCE) BY 50
...",
While executing the IMPLIED-DO clause "((FORMAT OSTREAM ~a~% (SUBSEQ SEQUENCE POS (+ 50 P..."
After executing the loop 23 times, an error was detected:
In SUBSEQ, `end' (1200) is beyond the end of the sequence (1167).>>>
<<< Use (EXPLAIN) to see a stack trace. >>>
Oops! I guess that we need to ensure that we don't try to subseq off
the end of the sequence. We can add a clever little condition for that:
>>(with-open-file (ostream "cxl.fasta" :direction :output :if-exists :supersede)
>> (xloop for gene in cxl-genes
>> as sequence = (extract-sequence gene)
>> as length = (length sequence)
>> (format ostream ">~a~%" (#^fname gene))
>> (xloop for pos from 0 to length by 50
>> (format ostream "~a~%"
>> (subseq sequence pos
>> (min length (+ 50 pos)))))))
>> (list-file-contents "cxl.fasta")
----- cxl.fasta -----
>S6803.sll0578
ATGGAAACAAAATTAACCACAGTGGGGGTAATTGGTGGTGGACAGTTGGC
CTGGATGATGGCCCAGGAAGCCCCCCGATTGGGATTAAAACTTGCAGTGC
AAACCCCTGGGGAAAGTGATCCGGCCGTGGCATTGGCGGACAAAGTGGTA
TTGACGGCGATCGCCGATGGGGAAGGAACTAGGGAGTTAGCAGAGCACTG
...etc.
CCGCTCTGCCCCATAGCCACGTCCATTGGTACGGCAAAGGAGACTGTCGT
CCCGGTCGGAAGCTGGGCCATGTGACTTTGTTAAACCCTGATGTTGAATC
GGAACCTTCCACTGCCTGGGCTGAAGATTTGGTGAAACAAGTAGAGGCGA
TTTGGTATCCGGATTAA
>S6803.slr0662
ATGGAAGGGCAGTCAATCGAACTAGAACTAAGTGTCATGGCAATGCCGGA
GTTAATCGACAGTACTGAAGCAGGCCATACCGCCGGGGTGAAAACTGATT
...etc...
GAAATGGACCGGGTTTTGGCTTTGGACGGGGTGCAACTAATCGGAGTTAA
TAACCGTAATTTGCAAACCTTCACCGTTGATCTGCAAACCACAGAGGATC
TTTTTGCCCAACGACGGGAGCAATTAA
That looks good, but we ought to check that it's not losing characters
at the line turns, and that it works when there's an even multiple of
50. We'll do that by making up a sequence with exactly 200 character,
and trying out our loop on that.
>> (setq test-sequence
>> (xloop with result = ""
>> for i from 1 to 200
>> (setq result (format nil "~a~a" result (mod i 10)))
>> finally (return result)))
; While compiling (:ANONYMOUS-LAMBDA 147):
Warning:
Within the loop "(LOOP WITH RESULT = FOR I FROM 1 TO 200
(SE...",
contains a WITH clause!
A WITH clause is executed exactly once before the loop starts,
not each time through the loop (like FOR or AS clauses are).
Since WITH is easy to confuse with FOR or AS, we ask you to
use INIT or INITIALIZE instead of WITH, and if you do, you won't
see this obnoxious warning.
:: "123456789012345678901234567890123456789012345678901234567890..."
Well, it worked, but let's take the obnoxious warning's word for it,
and use init instead of with:
>> (setq test-sequence
>> (xloop init result = ""
>> for i from 1 to 200
>> (setq result (format nil "~a~a" result (mod i 10)))
>> finally (return result)))
:: "123456789012345678901234567890123456789012345678901234567890..."
Much nicer. Okay, now we can test the relevant part of our writing
loop. We won't bother writing to a file, just print it out on the
screen:
>> (let ((length (length test-sequence)))
>> (xloop for pos from 0 to length by 50
>> (format t "~a~%"
>> (subseq test-sequence pos
>> (min length (+ 50 pos))))))
::
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
12345678901234567890123456789012345678901234567890
Looks right.
Accessors and Setf
One of the cool things about Lisp is that is has this duality between
accessing things and setting them. For example, you access the value
of a symbol (used as a variable) by naming the symbol, and you set it
using setf:
>> (setf myvar 5)
:: 5
>> myvar
:: 5
Well, it turns out that you can do that for any single
structure reference! Watch:
>> letters
:: (a bee see dee eee elephant gee! ach eye jay kay eel emu en oh!
pee que are es tea ewe vee double-ewe ex why? zeeeeeeee)
>> (elt letters 11)
:: eel ; remember, the count starts at zero!
>> (setf (elt letter 11) 'wheel)
:: wheel
>> letters
:: (a bee see dee eee elephant gee! ach eye jay kay wheel emu en oh!
pee que are es tea ewe vee double-ewe ex why? zeeeeeeee)
See, the setf changes the accessed element (the (elt ... 11) or the
12th element because of starting at zero!) to the new value!)
>> (setf mystring "this is my string")
:: "this is my string"
>> mystring
:: "this is my string"
>> (elt mystring 2)
:: #\i
>> (elt mystring 3)
:: #\s
>> (setf (elt mystring 2) #\a)
:: #\a
>> (setf (elt mystring 3) #\t)
:: #\t
>> mystring
:: "that is my string"
Warning!  So once you've changed the symbol value, list, or string
the old value is gone gone gone! This
could be relevant to your algorithm, so it's worth mentioning twice...
Hash Tables
The next data structure we're going to study is the hash
table. A hash table is a lookup table that associates anything
with anything....well, okay, not anything, like, you probably
can't associate your knee with the department of defense, much as you
might like to... but any lisp thing with any other lisp thing. The way
this works is that you first tell lisp that you have a hash table, and
usually you'll want to assign it to a symbol (that is, a variable) so
that you can conveniently refer to it:
>> (setf my-table (simple-hash-table))
SIMPLE-HASH-TABLE is a function that creates and returns the most
common type of HASH table (a simple one!) ... this implies that there
are complex hash-tables, which there are, but 99% of the time you just
want a simple one.
:: #<EQUAL hash-table with 0 entries @ #x8f0e809a>
That's the printed-out form of a hash table. Don't worry about what it
means for now, just notice that there are "0 entries", which is good
because we haven't put anything into it yet!
>> (gethash key table)
where KEY is the thing that you want to be the lookup key. For
example, if you want to look me up by my phone number, you could do this:
>> (setf (gethash 'jeff my-table) 5551212)
(That's not my real phone number!)
>> (gethash 'jeff my-table)
:: 5551212
And we'll notice that if we just look at the table, there's now 1 entry:
>> my-table
:: #<EQUAL hash-table with 1 entries @ #x8f0e809a>
>> (clrhash my-table)
>> my-table
:: #<EQUAL hash-table with 0 entries @ #x8f0e809a>
>> (xloop for gene in cxl-genes
>> (setf (gethash gene my-table) (length gene)))
<<< Evaluation failed. Actual error: >>>
<<<
Within the loop "(LOOP FOR GENE IN CXL-GENES
(SETF (GETHASH G...",
While executing the IMPLIED-DO clause "((SETF (GETHASH GENE MY-TABLE) (LENGTH GENE)))"
After executing the loop 0 times, an error was detected:
attempt to take the length of a non-sequence: #$S6803.sll0578>>>
<<< Use (EXPLAIN) to see a stack trace. >>>
Oops! We need the length of the gene sequence, not the gene:
>> (xloop for gene in cxl-genes
>> (setf (gethash gene my-table)
>> (length (extract-sequence gene))))
:: NIL
As usual, the loop didn't return anything. Did it actually do
anything? Let's see:
>> my-table
:: #<EQUAL hash-table with 19 entries @ #x8f1a810a>
Sure did: There are now 19 entries in the table. We can see them with
the help of XLoop:
>> (xloop for (key value) in my-table
>> do (print (list key value)))
::
(#$S6803.sll0578 1167)
(#$S6803.slr0662 2088)
(#$S6803.slr0546 888)
(#$S6803.sll0901 531)
(#$S6803.sll0504 1410)
(#$S6803.slr0536 1053)
(#$S6803.sll0892 438)
(#$S6803.sll0838 696)
(#$S6803.sll1641 1404)
(#$S6803.slr1099 621)
(#$S6803.slr1312 1980)
(#$A7120.all3569 384)
(#$A7120.alr2983 717)
(#$A7120.alr2945 1503)
(#$A7120.all0395 1617)
(#$Tery.Te?6781 456)
(#$Tery.Te?6780 444)
(#$Tery.Te?4796 207)
(#$Tery.Te?4797 333)
> NIL
Perfect! (Again, this didn't return the list, just printed it out; Do
you remember how to actually return the list?)
>> (search "TTATT" "ACTCCTCTATCTATACTTATTCTCTATATACGATGACTAGA")
:: 16
>> (search "TTATT" "ACTCCTCTATCTATACTTAATCTCTATATACGATGACTAGA")
:: NIL
If the string is found, it tells us the position, ortherwise it
returns NIL -- for not found. Let's put together some of what we've
done thus far to solve this problem easily.
>> (clrhash my-table) ; always remember to clear your tables!
:: #
So, the PUSH pushed (just like its name!) each symbol (A and then B)
on to the front of a list being built up in the table under the given
key (ANY-KEY in this case)
>> (clrhash my-table) ; always remember to clear your tables!
:: #
Great! So as it turns out, TTCTT isn't all that common a motif among
these genes!
Some Practice
There is a function called "TRANSLATE-D/RNA-TO-AA" which ... well,
which does the obvious thing:
>> (TRANSLATE-D/RNA-TO-AA (extract-sequence #$S6803.slr0546))
:: "MEIRRRPPNPPIKVDILQYQIKHPEAAPRHILEEIVW..."
>> (defun xaa-length (gene)
>> (length (TRANSLATE-D/RNA-TO-AA (extract-sequence gene)
>> :if-partial-codon :warn :if-unknown-codon :replace)))
Does it work?
>> (xaa-length #$S6803.slr0546)
:: 296
Okay, so we know enough now to be able to figure out how to call this
function on every gene in an organism.
;;; First let's set a variable to represent the organism's
;;; genes, so that we don't have to keep typing that:
>> (setq syn6803 (load-organism :syn6803))
:: #$synechocystis_pcc6803
>> (setq syngenes (#^genes syn6803))
:: (#$S6803.slr0612 #$S6803.slr0613 #$S6803.sll0558 #$S6803.sll1214
...)
;;; And we're only going to use the first ten genes for these examples,
;;; so let's reset the variable, and just drop the rest:
>> (setq syngenes (first-n 10 syngenes))
:: (#$S6803.slr0612 #$S6803.slr0613 #$S6803.sll0558 #$S6803.sll1214
#$S6803.sll1213 #$S6803.sll1212 #$S6803.slr1311 #$S6803.slr1312
#$S6803.sll1209 #$S6803.slr1315)
Okay, now let's do some iteration!
>> (xloop for gene in syngenes
>> collect (xaa-length gene))
:: (231 174 234 359 313 363 361 660 670 203)
Here's another way that's very slightly shorter using a function
called "mapcar" that applies function to every element of the list:
>> (mapcar #'xaa-length syngenes)
:: (231 174 234 359 313 363 361 660 670 203)
The #' part is the way you tell Lisp that a symbol refers to a
function.
More XLoop Examples
Here are some complex Xloop uses, with explanations:
;; Collect all numbers below 1000 which are squares and which
;; are divisible by 3.
>> (xloop for j from 1
>> as k = (* j j)
>> until (> k 1000)
>> when (zerop (mod k 3))
>> collect k)
:: (0 9 36 81 144 225 324 441 576 729 900)
The above illustrates the use of WHEN inside LOOP to control the items
collected, and the use of UNTIL to control the termination of the
loop. Also, note how AS is used to define a temporary variable which
gets reset each time through the loop. (You'll see both FOR and AS
used in this way. FOR and AS are completely interchangable;
They mean exactly the same thing! This is not true for another
similar-looking construct: WITH. Whereas FOR/AS indicate a term is to
be calculated each time through the loop, WITH only does the
calculation the first time, and not again! You can get yourself
into all sorts of trouble by confusing FOR/AS with WITH, which is why
XLOOP wants you to use INIT as a substitute for WITH.
;; Print some random numbers
>> (xloop with r1 = (random 100)
>> for j from 1 to 10
>> as r2 = (random 100)
>> collect (list r1 r2))
:: ((82 77) (82 72) (82 10) (82 34) (82 46) (82 62) (82 80) (82 70) (82 66) (82 99))
(You'll obviously get a different list because the numbers are randomly generated!)
Notice that while R2 changes each time through the loop, R1 does not.
A WITH-clause evaluates its expression once and only once,
conceptually before the loop actually begins. An AS-clause evaluates
its expression each time through the loop. Therefore, a
WITH-expression is very much like using a LET surrounding the entire
loop.
>> (setf random-pairs
>> (xloop with r1 = (random 100)
>> for j from 1 to 10
>> as r2 = (random 100)
>> collect (list r1 r2)))
:: ... some other random pairs ...
And now we'll do something called "destructuring", where we bind two
different variables AT THE SAME TIME to each member of the pair:
>> (xloop for (first-number second-number) in random-pairs
>> do (format t "The first number is ~a, the second number is ~a.~%"
>> first-number second-number))
See what happened? Each time through the loop, the variables
FIRST-NUMBER and SECOND-NUMBER got set ("bound", in lisp-ese) to each
of the values in the pairs.
>> (let ((contig-genes-list
>> ;; Initilize CONTIG-GENES-LIST to pair with 0 counts:
>> (xloop for cs in (#^Contiguous-Sequences #$synechocystis_pcc6803)
>> collect (list cs 0))))
>> ;; Now run through all the genes:
>> (xloop for gene in (#^Genes #$synechocystis_pcc6803)
>> do
>> (incf (second (find (#^Contiguous-Sequence gene)
>> contig-genes-list
>> :key 'first
>> ))))
>> ;; Finally, Print the results:
>> (xloop for (contig gene-count) in contig-genes-list ; <- DESTRUCTURING!
>> do
>> (format t "~D genes in ~A~%" gene-count contig)
>> ))
3313 genes in #$S6803.chromosome
106 genes in #$S6803.pSYSA
49 genes in #$S6803.pSYSG
132 genes in #$S6803.pSYSM
110 genes in #$S6803.pSYSX
6 genes in #$S6803.pCC5.2
2 genes in #$S6803.pCA2.4
3 genes in #$S6803.pCB2.4
The above has a bunch of interesting features, including demonstrating
how loops can be embedded in other code (the LET both declares and
sets the value of the temporary variable at the same time!), and
another example of destructuring.
>> (xloop for j from 10 by -2
>> for x in '(a b c d e) by 'cddr
>> do (print (list j x)))
::
(10 A)
(8 C)
(6 E)
[OPTIONAL SECTION!] Some totally confusing things about strings:
'(#\a #\space #\l #\i #\s #\t #\?)
Notice that #\space is a single cahracter (a single space); Some
characters are written out like that. Just to prove the point that
strings are made up of characters, we'll use the ELT function, which
gets things out of an array to get some of the characters out of the
array that is a string:
>> (setf my-string "this is an array of chars")
:: "this is an array of chars"
>> (elt my-string 4)
:: #\Space
>> (setf (elt my-string 4) #\-)
>> my-string
"this-is an array of chars"
Woah! What was that last thing!? We used SETF on an expression
instead of on a symbol! Actually SETF works that way -- it's sort of
of magical. Pretty much any simple expression that accesses something
(like ELT accesses the elements of an array) can be SETF'ed to change
the thing they access. Above we accessed the 5th element of the array
my-string, and then used SETF to change it!
>> (setf my-string "this string has a \" in it")
:: "this string has a \" in it"
>> (elt my-string 18)
#\"
Okay, so there's the quote. Note that it came out as a #\" char, just as
in the previous example.
>> "\\a\\\\b"
That's a string with five characters, a backslash, an 'a', two more
backslashes, and a 'b'. The char: #\\ is the single character
backslash (as opposed to a string with a single backslash character,
"\\".
>> (length "\\a\\\\b")
:: 5
To create a string with a Tab character in it you need to do something like
>> (one-string "abc" #\Tab "def")
Or:
>> (concatenate 'string "abc" (string #\Tab) "def")
What aspects of this tutorial could be improved? Does it fit well
with the previous tutorials? Does it need something introduced before
hand that we failed to introduce? Any typos or confusing parts? Were
the exercises useful? Any other feedback?


Telemedicine is here to provide you a complete healthcare services virtually. Healthcare providers are rapidly deploying new virtual workflows due to circumstances resulting from COVID-19 (coronavirus disease) to reduce the risk of transmission to healthy patients. Here you’ll find resources to help you manage the change - from getting your clinicians, care team, patients and families comfortable with virtual consults, to guidance for IT on rapid deployment considerations. We’ll update this page regularly – so check back soon to see what’s new.
Resources
Applicant List
About Us


Triangular lattice AF with easy plane anisotropy
We create a triangular lattice in the ab-plane with Cr3+ magnetic atoms with spin quantum number S=3/2.
Contents
Define the lattice
tri = spinw; tri.genlattice('lat_const',[3 3 4],'angled',[90 90 120]) tri.addatom('r',[0 0 0],'S',3/2,'label','MCr3','color','orange') tri.gencoupling plot(tri,'range',[2 2 1])
Magnetic Hamiltonian
We create first neighbor natiferromagnetic interactions in the ab-plane with J = 1 meV and a weak easy-plane anisotropy in the ab-plane. On the crystal structure plot, the red ellipsoids symbolize the easy-plane anisotropy, where easy directions are shown by the longer principal axis directions of the ellipsoid.
tri.addmatrix('value',1,'label','J','color','SteelBlue') tri.addmatrix('value',diag([0 0 0.2]),'label','D','color','r') tri.addcoupling('mat','J','bond',1) tri.addaniso('D') plot(tri,'range',[2 2 1])
Magnetic structure
we define the 120 degree ground state magnetic structure in the ab-plane with ordering wave vector of k=(1/3,1/3,0). Due to the anisotropy, the normal vector to the spin plane is n=(0,0,1) and we can use a single unit cell to describe the magnetic structure, since it is a single-k structure: nExt=(1,1,1).
tri.genmagstr('mode','helical','S',[0; 1; 0],'k',[1/3 1/3 0],'n', [0 0 1]); plot(tri,'range',[2 2 1],'magColor','purple','baseShift',[0;-1;0],'atomLegend',false)
Spin wave spectrum
We calculate the spin wave spectrum using the incommensurate magnetic structure in the (H,H,0) reciprocal space direction. In this direction, there are two magnetic Bragg peaks at (1/3,1/3,0) and (2/3,2/3,0). There are three spin wave modes: S(Q,omega) and S(Q+/-k,omega) due to the incommensurate ordering wave vector. There is one Goldstone mode at the magnetic Bragg peaks. By plotting only selected spin wave polarisations we can see, that the gapped modes at the Bragg peaks are polarised along the c-axis, while the Goldstone mode has a polarisation in the easy-plane.
triSpec = tri.spinwave({[0 0 0] [1 1 0] 500}); triSpec = sw_neutron(triSpec); figure sw_plotspec(triSpec,'mode','disp','axLim',[0 7],'colormap',[0 0 0],'colorbar',false) triSpec = sw_egrid(triSpec,'Evect',linspace(0,7,500),'component','Sperp'); figure sw_plotspec(triSpec,'mode','color','axLim',[0 2],'dE',0.4) triSpec = sw_egrid(triSpec,'Evect',linspace(0,7,500),'component',{'0.5*Sxx+0.5*Syy' 'Szz'}); figure sw_plotspec(triSpec,'mode','color','axLim',[0 1],'dE',0.4) sw_plotspec(triSpec,'mode','disp','axLim',[0 7],'colormap',[0 0 0],'colorbar',false,'lineStyle','-','legend',false)
Warning: To make the Hamiltonian positive definite, a small omega_tol value was added to its diagonal!
Plotting with Horace
The convoluted color spin wave spectra also can be plotted using the Horace package, see: [[http://horace.isis.rl.ac.uk]]. The spectrum will be calculated in the (H,K,0) plane and a constant energy cut is plotted. The disp2sqw_eval() function can be called Horace objects with any dimensions.
% Finite energy resolution is simulated by convoluting the spectra with a % Gaussian function, with the following FWHM. dE = 0.15; % The calculated spectra using the plotting function of Horace and assuming % Horace is installed and setup. Calculate spectra using disp2sqw_eval % Horace function. if ~exist('sqw','file') fprintf('Horace is not installed. Exiting....\n'); return end horaceObj = d3d(tri.abc,[1 0 0 0],[0,0.005,1],[0 1 0 0],[0,0.005,1],[0 0 0 1],[0,0.1,10]); horaceObj = disp2sqw_eval(horaceObj,@tri.horace,{'component','Sperp'},dE); cut1 = cut(horaceObj,[],[],[3.0 3.5]); % We use the honest colormap cm_inferno. plot(cut1) colorslider('delete') colormap(flipud(cm_inferno)) colorbar
Horace is not installed. Exiting....
Written by Sandor Toth 16-June-2014


bacci.giovanni.bio.sequencing
Interfaces
SequencePullStreamer
SequenceReader
SequenceStreamer
SequenceWriter
Classes
AppTest
FastaFileDereplicator
FastaSequenceWriter
FilePointerContainer
FrequencyPullStreamer
FrequencyTableWriter
RandomFastaSequenceStreamer
SequencePointerPullStreamer
SequencePullStreamerDecorator
SimpleSequencePullStreamer
UniFire


A responsive website is one that a user can view and will look good on any device. Through the implementation of media queries in css, a website can be resized -made bigger or smaller, even the content can be hidden and moved- so it looks good on any screen. It's important because it provides the user with optimal viewing, interaction, ease of reading and navigation with basically no effort on their part.
Designing a website with basically the smallest screen in mind first and then working your way up from there. From a developers perspective this is because mobile design is the hardest and once completed designing for other, larger devices will be easier. Also it means that because it is the smallest design, it will have only the esssential features so the developer has already designed the core of the 'user experience'. It is important because if a site is good on a mobile device it will translate well to all devices and designing within such small paramters means ruthless prioritisation of content - which is what the user of a site is there for, content.
Frameworks are basically prescribed CSS files that you integrate and use to style your website. The good thing about this is that it saves a lot of time and effort and lends itself well to the creation of a responsive website.The downside when implementing a framework is that if you want to style your content in a way that is different to the framework you have to overwrite the code yourself.
At its most basic level, a wireframe can be compared to an architectural blueprint. When designing a website a developer can't write blocks of code without knowing where it's going to go - much like an architect when it comes to building a house. Developers use it because it allows them to plan the layout and interaction of an interface without being distracted by style - colours, typeface choices etc.
I'm currently having difficulty with the nav bar on my homepage. I can't get the positioning right.


My AMPL page
AMPL is a mathematical programming system supporting
linear programming, nonlinear programming, and (mixed) integer programming. From the site:
AMPL is a comprehensive and powerful algebraic modeling language for linear and nonlinear optimization problems, in discrete or continuous variables.
Developed at Bell Laboratories, AMPL lets you use common notation and familiar concepts to formulate optimization models and examine solutions, while the computer manages communication with an appropriate solver.
AMPL's flexibility and convenience render it ideal for rapid prototyping and model development, while its speed and control options make it an especially efficient choice for repeated production runs.
See also
Note: In 2007/2008 I wrote quite a few AMPL models without the logic/CP extension. See My AMPL models (non CP) below for a listing of these non CP models.
In 2013 I tested this logical/CP extensions much more. It requires either gecode or ilogcp solvers; see the AMPL page "Logic" and Constraint Programming Extensions for details. These models are listed in My AMPL+CP models just below.
My AMPL+CP models
April/May 2013: Here is a list of AMPL models which use the "Logic" and Constraint Programming Extensions to AMPL. I have mostly tested the Gecode CP solver in AMPL, but also the IBM ILOG CP ilogcp solver. See code.google.com/p/ampl/ for gecode executables (to be used as an AMPL solver) and github.com/vitaut/ampl for source code. Also some models not using any logic/CP extensions was made and they are marked as "not CP". Many of these models has been ported from my MiniZinc models.
- a_puzzle.mod: "A puzzle" (8809 = 6, ....)
- a_round_of_golf.mod: A Round of Golf (Dell Logic Puzzles)
- all_interval.mod: All interval problem (series), (CSPLib problem 7)
- alldifferent_except_0.mod: "Decomposition" of global constraint
alldifferent_except_0
- appointment_scheduling.mod: Appointment scheduling (Stack Overflow)
- arch_friends.mod: Arch Friends (Dell Logic Puzzles)
- baby_sitting.mod: Baby Sitting (Dell Logic Puzzles)
- bales_of_hay.mod: Bales of hay puzzle
- breaking_news.mod: Breaking News (Dell Logic Puzzles)
- broken_weights.mod: Broken weights problem
- building_blocks.mod: Building blocks puzzle (Dell Logic Puzzles). See labeled_dice3.mod below for a general model.
- calculs_d_enfer.mod: Calculs d'enfer puzzle (from the NCL manual)
- car.mod: Car sequencing (OPL)
Data files:
- circling_squares.mod: Circling squares puzzle (Dudeney)
- circuit.mod: "Decomposition" of global constraint
circuit
(also the path)
- clock_triplets.mod: Clock Triplets problem (Dean Clark, Martin Gardner)
- coin_change.mod: Coins change problem
- combinatorial_auction.mod: Combinatorial Auction
Data files:
- costas_array.mod: Costas Array
- crew.mod: Crew allocation problem
- crypta.mod: Cryptarithmetic puzzle
- crypto.mod: Cryptarithmetic puzzle
- cur_num.mod: Curious numbers (Dudeney)
- devils_word.mod: Devil's word (c.f. Devil's word CGI program)
- divisible_by_9_through_1.mod: Divisible by base through 1 (for bases 2.. 10: mod 2 = 0)
- dudeney_numbers.mod: Dudeney numbers
- einav_puzzle.mod: Einav puzzle (from A programming puzzle from Einav)
- eq10.mod: Eq 10 (standard benchmark)
- eq20.mod: Eq 20 (standard benchmark)
- fancy.mod: Mr Greenguest puzzle ("fancy dress" problem)
- finding_celebrities.mod: Finding celebrities at a party (Uwe Hoffmann)
Data files:
- five_floors.mod: Five floors problem (Alexey Radul & Gerald Jay Sussman: "The Art of Propagator")
- fractions.mod: Fractions (Prolog benchmark, B-Prolog)
- futoshiki.mod: Futoshiki grid puzzle
Data files:
- four_islands.mod: Four Islands (Dell Logic Puzzle)
- general_store.mod: General Store problem (Sam Loyd)
- global_contiguity2.mod: "Decomposition" of global constraint
global contiguity
- golomb.mod: Golomb ruler problem (CSPLib #6)
- grocery.mod: Grocery problem (Oz)
- hamming_distance.mod: Hamming distance
- handshaking.mod: Halmos' handshaking problem
- heterosquare.mod: Heterosquare grid
- hidato.mod: Hidato puzzle
Data files:
- huey_dewey_louie.mod: Huey, Dewey, and Louie problem (Marriott & Stuckey "Programming with Constraints")
- isbn.mod: Some exploration of ISBN13
- jobs_puzzle.mod: Jobs puzzle (logical puzzle)
- just_forgotten.mod: Just forgotten puzzle (Enigma 1517)
- kakuro2.mod: Kakuro grid puzzle
- killer_sudoku.mod: Killer Sudoku
- labeled_dice.mod: Labeled dice
- labeled_dice2.mod: Labeled dice, symbolic version
- labeled_dice3.mod: Labeled dice, symbolic and general version
Data files:
- langford.mod: Langford's number problem (CSPLib problem 24)
- langford1.mod: Langford's number problem, simpler version (not CP)
- latin_square_card_puzzle.mod: Latin square card puzzle
- lectures.mod: Simple lecture scheduling problem (Biggs: "Discrete Mathematics")
- lecture_series.mod: Lecture Series (Dell Logic Puzzles)
- magic_hexagon.mod: Magic hexagon (CSPLib)
- magic_hexagon2.mod: Magic hexagon, symbolic version (CSPLib)
- magic_sequence.mod: Magic sequence (CSPLib)
- magic_square.mod: Magic squares
- magic_square_and_cards.mod: Magic square and cards (Martin Gardner)
- mamas_age.mod: Mama's age (Dudeney)
- map.mod: Simple map coloring exampleq
- map2.mod: Simple map coloring example (alternative encoding and some more countries tha map.mod)
- marathon2.mod: Marathon puzzle (XPress example)
- minesweeper.mod: Minesweeper puzzle
Data files:
- monks_and_doors.mod: Monks and doors problem
- mr_smith.mod: Mr Smith problem (IF Prolog)
- nqueens_cp.mod: N-queens problem
- number_of_days.mod: Number of days problem (knapsack) (Nathan Brixius)
- number_square.mod: Number square problem (Pascal Van Hentenryck, OPL book)
- olympic.mod: Olympic puzzle
- organize_day2.mod: Scheduling, organizing a day (ECLiPSe)
- pair_divides_the_sum.mod: Pairs divides the sum (comp.lang.prolog)
- partition_into_subsets_of_equal_values.mod: Partition into subset of equal sums
Data files:
- perfect_square_sequence.mod: Perfect square sequence
- pert.mod: Simple PERT problem (Pascal Van Hentenryck)
- photo_problem.mod: Photo problem (Oz)
Data files:
- picking_teams.mod: Picking teams (David Curran)
- place_number.mod: Placing Number Puzzle
- quasigroup_completion.mod: Quasigroup completion problem
Data files:
- rot13.mod: Rot 13 (Caesar ciper) (not CP)
- safe_cracking.mod: Safe cracking puzzle (Mozart/Oz primer)
- schedule1.mod: Scheduling problem, using (a decomposition of)
cumulative
constraint
- schedule2.mod: Scheduling problem (Dennis E. Sasha)
- scheduling_speakers.mod: Scheduling speakers (Rina Dechter)
- secret_santa.mod: Secret Santa problem
- secret_santa2.mod: Secret Santa problem II (optimize "Secret Santa distance")
- sicherman_dice.mod: Sicherman's dice
- social_golfers1.mod: Social golfers
- sonet_problem.mod: SONET problem
- strimko2.mod: Strimko grid puzzle
Data files:
- ski_assignment_problem.mod: Ski assignment problem
- stuckey_seesaw.mod: Seesaw placement problem (Marriott & Stuckey: Programming with Constraints)
- sudoku_cp.mod: Sudoku solver
Data files:
- survo_puzzle.mod: Survo puzzle
Data files:
- talisman_square.mod: Talisman square
- timpkin.mod: Mrs Timpkin's Age problem (Dudeney)
- torn_number.mod: Torn number problem (Dudeney)
- traffic_lights.mod: Traffic lights problem (CSPLib #16)
- tourist_site_competition.mod: Tourist Site Competition
- twin_letters.mod: Twin letters puzzle
- wedding_optimal_chart.mod: Finding an optimal wedding seating chart
- who_killed_agatha.mod: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery)
- young_tableaux.mod: Young tableaux and partition
- zebra_cp.mod: Zebra problem ("Who owns the Zebra? Who drinks the water?")
My AMPL models (non CP)
Here are some of my AMPL models, many where written in autumn 2007 or spring 2008 when I studied (privatly) Operational Research and LP/MIP (after that I mostly used Constraint Programming systems such as
MiniZinc for solve these kind of problems).
Quite a few models are translations of Martin Chlond's models Integer Programming in Recreational Mathematics. Please note that many of these models do not use the newer Constraint Programming support in AMPL. See My AMPL+CP models above for this.
- 3_jugs.mod: 3 jugs problem (as shortest path problem)
- 50_puzzle.mod: Fifty puzzle (Martin Chlond)
- 5x5_puzzle.mod: Five puzzle (Martin Chlond)
- abbots_puzzle2.mod: The Abbott's Puzzle (Martin Chlond)
- abbots_puzzle.mod: The Abbott's Puzzle (Martin Chlond)
- abbott.mod: The Abbott's Window (Martin Chlond)
- assignment2.mod: Assignment problem (Winston's swimming team example)
- assignment3.mod: Assigment problem (Winston, celebreties on an island)
- assignment.mod: Assignment problem (Winston)
- ballistic.mod:
- bananas.mod: Bananas problem.
- birthdays_coins.mod: Tommy's Birthday Coins (Martin Chlond)
- book_buy.mod: Book buy puzzle (Martin Chlond)
- box.mod: Design a box at minimum cost (Lingo)
- branch_and_bound.mod: Branch and bound (Winston)
- branch_bound_taha.mod: Branch and bound (Taha)
- building_design.mod: Optimize building a building
- bus_scheduling.mod: Bus scheduling (Taha)
- capital_budget2.mod: Capital Budget (Winston)
- capital_budget.mod: Capital Budget (Winston)
- change_making.mod: Change Maker Problem (Martello: "Knapsack Problems")
- chessset.mod: Chess set problem (XPress)
- coin_change2.mod: Coin Change
- coin_change.mod: Coin Change
- coin_puzzle2.mod: Lewis Carroll coin puzzle (Martin Chlond)
- coins.mod: Coin puzzle (Martin Chlond)
- coins2.mod: Coins Problem (Martin Chlond)
- coins3.mod: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro
- coins_grid.mod: Coins Grid problem (Tony Hurlimann)
- color_simple.mod: Simple coloring of a map (Murty)
- cookie_bake_off.mod: Cookie Bake Off problem (PuzzlOr)
- critical_path1.mod: Critical Path (Winston)
- crowd.mod: The crowded board (Martin Chlond)
- cutting_stock_winston.mod: Cutting stock problem (Winston)
- cyclohexane.mod: Cyclohexane problem (Dudeney)
- dakota_furniture.mod: Optimization problem (Winston)
- debruijn.mod: de Bruijn sequence (graph)
- defending_castle.mod: Defending the Castle (Cut the knot)
- diet_small.mod: Diet problem
- dinner.mod: A dinner problem
- dqueens.mod: Dudeney's queen placement problem (Martin Chlond)
- dress_party.mod: Dressing party (Mr Greenguest problem) (LPL)
- dudeney_bishop_placement1.mod: Dudeney's bishop placement problem I (Martin Chlond)
- dudeney_bishop_placement2.mod: Dudeney's bishop placement problem II (Martin Chlond)
- dynamical_optimization1.mod: Dynamical optimization
- dynamical_optimization2.mod: Dynamical optimization
- earthlin.mod: Earthlings (Martin Chlond)
- egg_basket.mod: Egg basket puzzle (Martin Chlond)
- einstein_hurlimann.mod: Einstein puzzle (variant of Zebra puzzle)
- elevator.mod: A Tokyo Elevator Puzzle
- enigma.mod: Enigma (Martin Chlond)
- evens.mod: Evens puzzle 2 (Martin Chlond)
- evision.mod: Equal Vision (Martin Chlond)
- fill_a_pix.mod: Fill-a-pix (not CP)
Data files:
- five.mod: 5 X 5 puzzle v 2 (Martin Chlond)
- games.mod: Simple game theory example (Vanderbei "Linear Programming - Foundations - and Extensions", page 147ff)
- game_theory_taha.mod: Game theory, zero sum game (Taha, Operations Research)
- giapetto.mod: Simple optimization problem of maximizing profit
- goal_programming1.mod: Goal programming (Winston)
- gomorys_cut.mod: Gomory's cut (small example)
- hitchcock_transporation_problem.mod: Hitchcock-Koopmans transportation problem
- honey_division.mod: Honey division puzzle (Martin Chlond)
- hurlimann_clarke_tobacco.mod: Clarke's Tobacco problem (Hurlimann)
- hurlimann_math01.mod: Tobacco problem (Hurlimann)
- hurlimann_math02.mod: Twelve problem (Hurlimann)
- hurlimann_math03.mod: Eggs problem (Hurlimann)
- ickelinj.mod: Nonlinear problem
- jive_turkeys.mod: Jive turkeys (Martin Chlond)
- joshua.mod: Joshua and his rats (Martin Chlond)
- knapsack.mod: Knapsack problem. Data instances: knapsack2.dat , knapsack3.dat , knapsack4.dat ,
- knapsack.dat
- knapsack5.mod: Knapsack problem
- knight_domination_puzzle.mod: Knight domination puzzle - all squares threatened (Martin Chlond)
- knight_domination_puzzle2.mod: Knight domination puzzle - all squares threatened (alternative model)
- kntdom.mod: Knight domination puzzle - all squares threatened (Martin Chlond)
- kqueens.mod: Kraitchik's queen placement problem (Martin Chlond)
- lccoin.mod: Lewis Carroll coin puzzle (Martin Chlond)
- least_diff2.mod: Least diff problem: What is the smallest difference between two numbers X - Y if you must use all the digits (0..9) exactly once?
- least_diff3.mod: Least diff problem, variant
- least_diff4.mod: Least diff problem, variant
- least_square_optimeringslara_286.mod: Least sqauare (Lundgren, Rönnqvist, Värbrand: Optimeringslära)
- least_square_winston.mod: Least square problem (Winston)
- lights.mod: Lights on puzzle (Martin Chlond)
- magic.mod: Magic square, integer programming (GLPK)
- magic_square2.mod: Magic squares
- magic_square_taha.mod: Magic squares
- mango_puzzle.mod: Mango puzzle (Martin Chlond)
- marathon.mod: Marathon puzzle (XPress example), MIP model
- max_flow_winston1.mod: Maximum flow problem (Winston)
- max_flow_winston2.mod: Maximum flow problem (Winston)
- maximum_flow.mod: Maximum flow problem
- minimum_cost_network_flow_problem1.mod:
- monte_carlo.mod: , monte_carlo.run:
- murty_781.mod: Coin Bags problem (subset sum) (Murty)
- murty_782.mod: Another subset sum problem (Murty)
- nim.mod: A Nimatron (Martin Chlond)
- nlp_winston_617.mod: Nonlinear problem (Winston)
- non_dominating_queens.mod: Non-dominating queens problem (Martin Chlond)
- nonlin1.mod: Nonlinear problem (Bazaras)
- nonlin2.mod: Nonlinear problem (Taha)
- nonlin3.mod: Nonlinear problem
- nonlin4_winston_656.mod: Nonlinear problem (Winston)
- nonlin5.mod: Nonlinear problem
- nonlin_optimeringslara_288.mod: Nonlinear problem
- nonlin_optimeringslara_555.mod: Nonlinear problem
- nonlin_sin.mod: Nonlinear problem
- onroad.mod: On the road (Martin Chlond)
- optimeringslara_126.mod: Sensitivity analysis
- optimeringslara_386.mod: Integer problem
- organize_day.mod: Scheduling, organizing a day
- pigeon_hole.mod: Pigeon hole problem
- pilgrim.mod: The Riddle of the Pilgrims (Martin Chlond)
- post_office_problem2.mod: Post office problem (Winston)
- post_office_problem.mod: Post office problem (Winston)
- public_school_problem.mod: Public School Problem (Martin Chlond)
- puzzle1.mod: Yet another column/row sum problem
- remainder_puzzle.mod: Remainder puzzle (Martin Chlond)
- remainder_puzzle2.mod: Remainder puzzle (Kordemsky)
- rosebush.mod: A Nimatron (Martin Chlond)
- sendmore_hurlimann.mod: SEND+MORE=MONEY
- send_more_money2.mod: SEND+MORE=MONEY
- send_more_money3.mod: SEND+MORE=MONEY
- send_more_money4.mod: SEND+MORE=MONEY
- sensitivity_analysis.1.mod: Sensitivity Analysis)
- seseman.mod: , Seseman Convent problem (run file: seseman.run: )
- set_comparison.mod: Set comparisons in AMPL
- set_covering3.mod: Set covering, senators making a committe (Murty)
- set_covering4.mod: Set covering problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära"), requires set_cov1.dat)
- set_covering_deployment.mod: Set covering deployment
- set_covering_opl.mod: Set covering: workers building a house (OPL)
- set_covering_skiena.mod: Set covering (Steven Skiena)
- set_covering_winston1.mod: Set covering, placing firestations (Winston)
- set_packing.mod: Set packing
- shortest_path1.mod: Shortest path problem, selling/buying a car (Winston)
- shortest_path2.mod: Shortest path problem (Winston)
- smullyan_portia.mod: Raymond Smullyan's Portia problems
- spreadsheet.mod: "Spreadsheet problem"
- squeens.mod: Schuh's queen placement problem (Martin Chlond)
- stamp_licking.mod: The gentle art of stamp-licking (Martin Chlond)
- subset_sum.mod: Subset sum (Murty)
- sum_squares.mod: Sum of squares problem
- taha_21.mod: Optimization problem (Taha)
- tea_mixing.mod: Dudeney's tea mixing problem (Martin Chlond)
- tobacco.mod: Clarke's tobacconist (Martin Chlond)
- tomography.mod: Discrete Tomography (one color model)
- transportation.mod: Transportation problem
- transshipment.mod: Transshipment problem (Winston)
- trial1.mod: The First Trial (Martin Chlond)
- trial2.mod: The Second Trial (Martin Chlond)
- trial3.mod: The Third Trial (Martin Chlond)
- trial4.mod: The Fourth Trial (Martin Chlond)
- trial5.mod: The Fifth Trial (Martin Chlond)
- trial6.mod: The Sixth Trial (Martin Chlond)
- trial12_variant.mod: The Logical Labyrinth (Martin Chlond)
- tsp_winston.mod: Travelling Salesman Problem, integer programming
- twelve.mod: Twelve draughts puzzle (Martin Chlond)
- warehouse_location.mod: Warehouse location problem (Winston)
- were2.mod: Werewolves II (Martin Chlond)
- were4.mod: Werewolves IV (Martin Chlond)
- williams_131.mod: Nonlinear problem (Williams)
- wine_cask_puzzle.mod: Wine Cask puzzle (Martin Chlond)
- winston373.mod: Row/Column sum puzzle (sub problem of transportation problem)
- work2.mod: Simple word problem (regarding workers)
- work3.mod: Simple word problem (regarding workers)
- work_hour.mod: Simple word problem (regarding workers)
- xkcd.mod: xkcd's knapsack problem (see the xkcd strip for the problem)
Also, see my other pages about Constraint Programming systems:
* My Constraint Programming Blog
* Constraint Programming
* Common constraint programming problems
* My MiniZinc page
* My Zinc page
* My JaCoP page
* My JaCoP/Scala page
* My Choco page
* My Gecode/R page
* My Comet page
* My Gecode page
* My ECLiPSe page
* My Tailor/Essence' page
* My SICStus Prolog page
* My Google CP Solver page
* My OscaR page
* My JSR-331 page
* My Numberjack page
* My AIMMS+CP page
* My B-Prolog page
* My Choco3 page
Back to my homepage
Created by Hakan Kjellerstrand hakank@gmail.com


Hacktoberfest Lottery
Number of tries:
0
Average response time:
0
ms
Last response time:
0
ms
YOU WON
Start!


@(breeder : BreederDetail, breed : Breed) @html5.render
Address:
Phone number:
Email address:
Website:


CS50's Introduction to Artificial Intelligence with Python
Search
general pattern:
- begin
- correct sequence of actions
- goal
agent - perceives the environment and acts upon the environment
state - configuration of the environment
initial state
actions - choices taken in any given state. fuctions. ACTIONS(s) -> set of actions that can be done in given state.
transition model. RESULT(s, a) -> state after performing action a
in state s
state space. graph
goal state. determines whether a state is a goal state.
path cost. numerical cost associated with a given path.
Search problem:
- initial state
- actions
- transition model
- goal test
- path const function
optimal solution
node:
- state
- parent
- action
- path cost
frontier - all that is to be explored:
- Start with initial state.
- Start with empty explored set.
- repeat:
- If empty, there is no solution.
- remove a single node from the frontier
- if it is a goal - we’ve found a solution
- add node to the explored set
- expand (look at all neighbours of) node, add resulting nodes to the frontier if not in the frontier and not in explored set.
search algorithms
- stack - last in first out. Used for frontier. So we get a depth-first search.
- breath-first search always expands the shallowest node in the frontier. Uses a queue (first-in first-out)
BFS finds always the optimal path. DFS might save you memory.
uninformed search - doesn’t use any problem specific knowledge. informed search:
- Greedy best-first search (GBF) - expand the node that is closest to the goal by using a heuristic function
h(n)
- Manhattan distance - distance between two points along axes of right angles.
A* search: expand the node with the lowest value of g(n) + h(n)
where g(n)
is the cost to reach node. Optimal if:
- h(n) is admissible (never overestimates the true cost) - should never think I’m further away from the goal that I actually am.
- h(n) is consistent. Cost c,
h(n) <= h(n') + c
adversarial search
minimax - X wants to maximize max(o)
, O wants to minimize the score min(o)
.
TicTacToe functions:
- PLAYER(s) - who’s turn is it?
- ACTIONS(s) - possible actions for a state
- RESULTS(s, a) - perform a action and return the state
- TERMINAL(s) - did we finish the game?
- UTILITY(s) - score for a state
optimizations:
- Alfa-Beta-pruning - remove (don’t consider) some of the nodes using already computed information.
Depth-Limited Minimax:
- evaluation function - evaluates expected utility of the game from a given state
Knowledge
knowledge-based agents
sentence - assertion about the world in a knowledge representation language
propositional logic - based on statements about the world.
logical connectives - not and or, -> (implication), <-> (biconditional)
implication (if then)
| P (premise) | Q (conclusion) | P->Q |
|---|---|---|
| false | false | true |
| false | true | true |
| true | false | false |
| true | true | true |
biconditional (if and only if)
| P | Q | P<->Q |
|---|---|---|
| false | false | true |
| false | true | false |
| true | false | false |
| true | true | true |
model - assignment of a truth value to every propositional symbol (possible world). Total possibilities number_of_values**variables
knowledge base (KB) - set of sentences known a by a knowledge agent to be true
entailment A |= B
(A entails B) - in every model (possible world) in which sentence A
is true, then B
is also true.
We want our AI to figure out what the possible entailments are. To infer, to draw conclusions. inference - deriving new conclusions from old ones.
Model Checking
To determine if KB |= alfa
:
- Enumerate all possible models
- If in every model where
KB
is true,alfa
is true, thenKB entails alfa
. - Otherwise
KB
does not entailalfa
.
alfa
is the query.
Knowledge Engineering
Example: clue (game):
- Establish propositional symbols
- add knowledge
- check_model
Inference Rules
Modus Ponens: application of implication
alfa -> beta
alfa
------------
beta
And Elimination
alfa AND beta
-------------
alfa
and the same for beta
.
Double Negation Elimination
NOT NOT alfa
------------
alfa
Implication Elimination
alfa -> beta
------------
NOT alfa OR beta
Biconditional Elimination
alfa <-> beta
---------------------------------
(alfa -> beta) AND (beta -> alfa)
De Morgan’s Law
NOT(alfa AND beta)
--------------------
NOT alfa OR NOT beta
Reverse De Morgan’s Law
NOT(alfa OR beta)
---------------------
NOT alfa AND NOT beta
Distributive Property
(alfa AND (beta OR gama)
----------------------------------
(alfa AND beta) OR (alfa AND gama)
works also when AND is exchanged with OR and vice versa.
Theorem Proving
- initial state: staring knowledge base
- actions: inference rules
- transition model: new knowledge after inference
- goal test: check statement we’re trying to prove
- path cost functions: number of steps in proof
Unit Resolution Rule
P OR Q
NOT P
--------
Q
In an OR clause the order of arguments doesn’t matter.
 (A OR B OR C) AND (D OR NOT E) AND (F OR G)
. Any sentence in logic can be converted into this.
Conversion to CNF:
- Eliminate bi-conditionals
- Eliminate implications
- Move NOT inwards using De Morgan’s Laws
Factoring removing duplicate variables.
Empty clause (()
) is always false.
Proof by contradiction: assume the opposite and if you can demonstrate it is a contradiction the thing we want to prove is true.
First-Order Logic
- Constant Symbols (Minerva, Gryffindor …)
- Predicate Symbol (Person, House, BelongsTo, …)
Example:
Person(Minerva) # Minerva is a person
House(Gryffindor) # Gryffindor is a house
NOT House(Minerva) # Minerva is not a house
BelongsTo(Minerva, Gryffindor) # Minerva belongs to Gryffindor
Minimizes the number of symbols needed.
Universal Quantification - true for all
Existential Quantification - true for some, at least one value
Uncertainty
Probability
Possible Worlds (Ω - omega). P(omega)
Probability: 0 <= P(omega) <= 1
, sum(P(omega)) == 1
unconditional probability: degree of belief in a proposition in the absence of any other evidence
conditional probability: we have some initial information about the world and how it works (evidence has been revealed to us). P(a | b)
Probability of a
given we already know that b
is true. Formula:
P(a|b) = P(a AND b) / P(b) # or
P(a AND b) = P(b) P(a|b) # or
P(a AND b) = P(a) P(b|a)
random variable: a variable with a domain of possible values it can take on. E.g.: traffic {none,light,heavy}
, probability distribution:
P(traffic = none) = .6
P(traffic = light) = .3
P(traffic = heavy) = .1
P(traffic) = <0.6, 0.3, 0.1> # equal but less verbose
independence: knowledge of one event doesn’t influence the probability of the other events. P(a AND b) = P(a) P(b)
. Example: roll of two dices.
Bayes’ Rule:
P(b|a) = P(b) P(a|b) / P(a)
Example: given clouds in the morning, what is the probability of the rain in the afternoon?
- 80% of rainy afternoons start with cloudy mornings.
- 40% of days have cloudy mornings
- 10% of days have rainy afternoons
Solution:
P(rain | clouds) = P(clouds | rain) P(rain) / P(clouds)
= 0.8 * 0.1 / 0.4
= 0.2
Knowing P(visible effect | unknown cause)
we can calculate P(unknown cause | visible effect)
.
Joint Probability
Example:
C = 0.4, not C = 0.6
R = 0.1, not R 0.9
R not R
C .08 .32
not C .02 .58
P(cloudy | rain) = P(cloudy, rain) / P(rain) # , = AND
= alfa P(C, rain) # alfa = normalization constant
= alfa <.08,.02>
= <.8, .2>
Probability Rules
Negation: P(not a) = 1 - P(a)
Inclusion-Exclusion: P(a OR b) = P(a) + P(b) - P(a AND b)
Marginalization: P(a) = P(a, b) + P(a, not b)
. Example:
P(C = cloud) = P(C = cloud, R = rain) + P(C = cloud, R = not rain)
= 0.08 + 0.32
= 0.4
Conditioning: P(a) = P(a|b)P(b) + P(a| not b)|P(not b)
Bayesian Networks
- data structures that represent the dependencies among random variables
- directed graph
- each node represents a random variable
- arrow from
X
toY
meansX
is a parent ofY
- each node X has a probability distribution
P(X | Parents(X))
Inference problem:
- Query
X
: variable for which to compute the distribution - Evidence variables
E
: observed variables for evente
- Hidden variables
Y
: non-evidence, non-query variable - Goal: Calculate
P(X | e)
Inference by Enumeration: P(X | e) = alfa P(X, e) = alfa sum_y(P(X, e, y)
Approximate Inference, e.g. by sampling.
Likelihood weighting:
- fix the values for evidence variables,
- sample the non-evidence variables using conditional probabilities of the Bayesian Network,
- weight each sample by its likelihood: the probability of all of the evidence.
Markov Models
Uncertainty over time. -> Huge amount of data / complexity.
Markov assumption: assumption that the current state depends on only a finite fixed number of previous states.
Markov chain: a sequence of random variables where the distribution of each variable follows the Markov assumption.
hidden state vs. observation. E.g. user engagement vs. website analytics or weather vs. people bringing umbrellas to the office. The AI doesn’t know the truth of the world (hidden state) all it has access to is some observation that is related to the hidden state.
Hidden Markov Model a Markov model for a system with hidden states that generate some observed event. Also often called Sensor Model.
sensor Markov Assumption: the assumption that the evidence variable depends only on the corresponding state.
Tasks:
- filtering: given observations from start until now calculate the distribution for current state
- prediction: … for a future state
- smoothing: … for a past state
- most likely explanation: … most likely sequence of states
Optimization
- choosing the best option from a set of options
local search: search algorithms that maintain a single node and searches by moving to a neighboring node. Most useful when we don’t care about the path but the solution only.
state-space landscape. Global minimum - cost function. Global maximum - objective function. We move to neighbours from current state.
hill climbing algorithm
function hill-climb(problem):
current = initial state of problem
repeat:
neighbor = highest valued neighbor of current
if neighbor not better than current:
return current
Hill climbing might get stuck at a local maxima. Therefore there are hill climbing variants:
- steepest-ascent: choose the highest-valued neighbor
- stochastic: choose randomly from higher-valued neighbors
- first-choice: choose the first-higher valued neighbor
- random-restart: conduct hill climbing multiple times
- local beam search: choose the
k
highest-valued neighbors
Real problem with hill climbing is that they never make a move that makes our position worse. And that’s what’s needed to get to a global maximum.
Simulated Annealing
- Early on, higher “temperature”: more likely to accept neighbors that are worse than current state
- Later on, lower “temperature”.
function SIMULATED-ANNEALING(problem, max):
current = initial state of problem
for t = 1 to max:
T = temperature(t)
neighbor = random neighbor of current
delta_e = how much better neighbor is than current
if delta_e > 0:
current = neighbor
with probability e**(delta_e/T) set current = neighbor
return current
Linear Programming
- Minimize a cost function
- With constraints
- With bounds for each variable
Example:
Cost function: 50x + 80y
Constraint: 5x + 2y <= 20
Constraint: 10x + 12y >= 90 -> (-10x) + (-12y) <= -90
Constraint Satisfaction
- Set of variables {X1, …, Xn}
- Set of domains for each variable {D1, D2, …, Dn} - possible values each of the variables can take on.
- Set of constraints C
hard constraints - must be satisfied in a correct solution
soft constraints - preferences
unary constraint - involves just a single variable, e.g.: A != monday
binary constraint - involves two variables, e.g.: A != B
node consistency: when all the variables in a variable’s domain satisfy the variable’s unary constraints. For each of possible nodes remove possible values of the domain so all the unary constraint are satisfied.
arc consistency
when all the values in a variables domain satisfy the variable’s binary constraints
function REVISE(csp, X, Y): # csp = constraint satisfaction problem
revised = false
for x in X.domain: # loop over all values of X's domain
if no y in Y.domain satisfies constraint for (X, Y):
delete x from X.domain
revised = true
return revised
function AC-3(csp):
queue = all arcs in csp
while queue non-empty:
(X, Y) = DEQUEUE(queue) # (X, Y) is an arc (or edge)
if REVISE(csp, X, Y):
if size of X.domain == 0:
return false
for each Z in X.neighbors - {Y}:
ENQUEUE(queue, (Z, X)) # removing X might not satistfy Z anymore
return true
AC-3 will not always solve the problem. What remains is a Search Problem:
- initial state: empty assignment (no variables)
- actions: add a
{variable = value}
to assignment - transition model: shows how adding an assignment changes the assignment
- goal check: check if all variables are assigned and all constraints satisfied
- path cost function: irrelevant (all paths have same cost)
Backtracking Search
function BACKTRACK(assignment, csp):
if assignment complete:
return assignment
var = SELECT-UNASSIGNED-VAR(assignment, csp)
for value in DOMAIN-VALUES(var, assignment, csp):
if value consistent with assignment: # doesn't violate any constraints
add {var = value} to assignment
result = BACKTRACK(assignment, csp)
if result != failure: return result
remove {var = value} from assignment
return failure
Inference: use Arc Consistency interleaved with search, so we backtrack less.
maintaining arc-consistency: algorithm for enforcing arc-consistency every time we make a new assignment. When we make a new assignment to X
, call AC-3
, starting with a queue of all arcs (Y, X)
where Y
is a neighbour of X
.
SELECT-UNASSIGNED-VAR heuristics:
- minimum remaining values (MRV) heuristic: select the variable that has the smallest domain
- degree heuristic: select the variable that has the highest degree (connected to the most other nodes)
DOMAIN-VALUES heuristics:
- least constraining value: return variables in order by number of choices that are ruled out for neighboring variables:
- try least-constraint values first
Learning, ML (learning from data and experience)
No explicit instructions how to perform a task, but give access to data and let the computer figure it out.
Supervised Learning
given a data set of input-output pairs, learn a function to map inputs to outputs.
classification: supervised learning task of learning a function mapping of an input to a discrete category. E.g. banknote -> counterfeit/real
nearest-neighbor classification: algorithm that, given an input, chooses the class of the nearest data point to that input:
- k-nearest-neighbour classification: …
k
nearest data points …- could be slow
Perceptron Learning
hypothesis function to determine on which side of boundary is the input. Example:
x1 = Humidity
x2 = Pressure
Weight Vector w: (w0, w1, w2)
Input Vector x: (1, x1, x2)
w * x: w0 + w1x1 + w2x2
h(x1, x2) = Rain if w0 + w1x1 + w2x2 >= 0 else no Rain
The goal of the ML algorithm is to learn what the Weight Vector will be.
General hypothesis form: h(x) = 1 if w*x >= else 0
perceptron learning rule: given data point (x, y)
update each weight according to: w_i = w_i + alfa(y - h_w(x)) * x_i
, which means w_i = w_i + alfa(actual value - estimate) * x_i
. alfa = learning rate (how quickly we’re going to update the weight values).
hard threshold vs. soft threshold (logistic regression)
Support Vector Machines
Can work in higher dimensions.
maximum margin separator: boundary that maximizes the distance between any of the data point.
Regression
Supervised learning task of learning a function mapping an input point to a continuous value.
Evaluating Hypotheses
Think of a Optimization Problem.
loss function: function that expresses how poorly our hypothesis performs.
0-1 loss function:
L(actual, predicted) =
0 if actual = predicted,
1 otherwise
L1 loss function:
L(actual, predicted) = |actual - predicted|
L2 loss function - penalizes much more harshly far away predictions:
L2(actual, predicted) = (actual - predicted)**2
overfitting - a model that fits too closely (little or no loss) to a particular data set and therefore may fail to generalize to future data.
regularization - penalizing hypotheses that are more complex to favor simpler, more general hypothesis. We want to give preference to a simpler solution which might generalize better: cost(h) = loss(h) + lambda*complexity(h)
holdout cross-validation - splitting data into a training set and a test set, such that learning happens on the training set and is evaluated on the test set. Downside: a fair amount of data is not used to train.
k-fold cross-validation - splitting data into k
sets, and experimenting k
times, using each set as a test once and using remaining data as a training test
Reinforcement learning
Given a set of rewards or punishments, learn what actions are to be taken in future:
Environment
/ \
action^ state_v, reward_v
\ /
Agent
Markov Decision Process model for decision-making, representing states, actions, and their rewards:
- Set of states
S
- Set of actions
ACTIONS(s)
- Transition model
P(s'|s, a)
- Reward function
R(s, a, s')
Q-Learning method for learning a function Q(s, a)
, estimate of the value of performing action a
in state s
. Overview:
- Start with
Q(s, a) = 0
for alls
,a
- When we take an action and receive a reward:
- Estimate the value of
Q(s, a)
based on current reward and expected future rewards. - Update
Q(s, a)
to take into account old estimate as well as our new estimate. - Formally:
Q(s, a) <- Q(s, a) + alfa(new value estimate - old value estimate)
Q(s, a) <- Q(s, a) + alfa((r + future reward estimate) - Q(s, a))
Q(s, a) <- Q(s, a) + alfa((r + max_a'(Q(s', a')) - Q(s, a))
Q(s, a) <- Q(s, a) + alfa((r + y*max_a'(Q(s', a')) - Q(s, a))
- to give preference to current rewards (y)
- Estimate the value of
alfa
represents how much we value new information compared to how much we value old information. alfa
of 1 means we only consider new information.
Greedy Decision-Making: when in state s
, choose action a
with highest Q(s, a)
Tension between Explore vs. Exploit (using knowledge we already have, which might not need to optional solution).
epsilon-greedy
- Set
epsilon
equal to how often we want to move randomly. - With probability
1 - epsilon
, choose estimated best move. - With probability
epsilon
, choose a random move. Esp. in the beginning.
function approximation - approximating Q(s, a)
, often by a function combining various features, rather than storing one value for every state-action pair.
Unsupervised Learning
given input data without any additional feedback, learn pattern.
clustering organizing a set of objects into groups in such a way that similar objects tend to be in the same group.
k-means clustering - algorithm for clustering data based on repeatedly assigning points to clusters and updating those cluster’s centers.
Neural Networks
- Neurons are connected to and receive electrical signals from other neurons.
- Neurons process input signals and can be activated.
pip install tensorflow-macos
Artificial Neural Network - mathematical model for learning inspired by biological neural networks:
- Model mathematical function from input to outputs based on the structure and parameters of the network.
- Allow for learning the network’s parameters based on data.
activation function - function that gets applied to the result and decides whether a threshold is passed (e.g. “it rains or not”).
Schematics for a very simple neural network:
w0
|
x1 \ |
g(w0 + w1*x1 + w2*x2)
x2 /
Neural network will learn what the values of w0
, w1
and w2
should be in order to get the results that we would expect. General formula g(sum(x_i*w_i) + w0)
.
gradient descent - algorithm for minimizing loss when training neural network. Gradient is going to tell us in which direction we should be moving the weights in order to minimize the loss.
General idea:
- Start with a random choice of weights
- Repeat:
- Calculate the gradient based on all data points: direction that will lead to decreasing loss (all data points - expensive operation).
- Update weights according to the gradient.
Stochastic Gradient Descent - s/all data points/one data point randomly/
Mini-Batch Gradient Descent - s/all data points/one small batch/
Perceptron: a single one is only capable of learning linearly separable decision boundary, because we’re taking linear combination of input.
multilayer neural network - artificial neural network with an input layer, an output layer, and eat least one hidden layer. Gives us the ability to model more complex function.
backpropagation algorithm for training neural networks with hidden layers. Key algorithm for making neural networks possible. Idea:
- start with a random choice of weights
- Repeat:
- Calculate error for output layer
- For each layer, starting with output layer and moving inwards towards earliest hidden layer:
- Propagate error back one layer.
- Update weights.
deep neural network - neural network with multiple hidden layers.
overfitting
dropout - temporarily removing units - selected at random - from a neural network to prevent over reliance on certain units.
computer vision computational methods for analyzing and understanding digital images.
image convolution - applying a filter that adds each pixel value of an image to its neighbors, weighted according to kernel matrix.
pooling reducing the size of an input by sampling from regions in the input. max-pooling chooses the maximal value in a each region.
convolutional neural network (CNN) - uses convolution, usually for analysing images.
image -> convolution -> pooling -> flatting -> neural network
General structure of NN: input -> network -> output
. This is a feed-forward neural network - NN that has connections only in one direction. Limitations: fixed shape (number of) input and output neurons.
Recurrent Neural Network - generates output that gets feds back into the network as input for future runs of the network:
/--\
v |
input -> network -> output
This allows to store state. This is particularly helpful when dealing with sequences of data.
Example: Microsoft’s Captionbot or analyzing videos.
1 -> N relationships as opposed to 1:1 from before.
N -> 1: e.g. classification of a voice from a audio sample
N -> N: e.g. google translate
Human Language
Common tasks:
- automatic summarization
- information extraction
- language identification
- machine translation
- named entity recognition
- speech recognition (Alexa)
- text classification
- word sense disambiguation
- …
syntax - structure
semantics - meaning
formal grammar a system of rules for generating sentences in a language.
Context-Free Grammar
Replacing one symbol with another symbol.
Non-terminal symbols (noun - N
, verb - V
) are used to generate terminal symbols (“she”, “saw”).
On the left we have always a non-terminal symbol, on the right of the arrow it could be either terminal or non-terminal symbols. E.g. NP -> N | D N
.
pip install nltk
n-gram
a contiguous sequence of n
items from a sample text. e.g.: character n-grams or word n-grams.
unigram - a contiguous sentence of 1 item from a sample text.
bigram - … 2 items …
trigrams - … 3 items …
Allows for segmentation of the text for analysis and while the AI might have not seen the whole sentence before, it is likely that it has encountered a N-gram from it before.
tokenization
the task of splitting a sequence of characters into pieces (tokens). E.g. to extra n-grams.
word tokenizations - splitting into words.
Markov Model
It will allow us to predict what the next unit will be.
pip install markovify
Text Categorization
a classification problem. E.g. spam/not spam. Positive / negative sentiment.
Bag-of-Words -model that represents text as unordered collection of words. Works pretty well for positive/negative sentiment approach.
Naive Bayes
How to not worry about multiplying by zero:
- additive smoothing - adding a value
alfa
to each value in our distribution to smooth the data. - Laplace smoothing - adding 1 to each value in our distribution, pretending that we’ve seen each value one more time than we actually have.
Naive Bayes basically looks for differentiating words (which have a big weight in one category and not so in others).
Information Retrieval
the task of finding relevant documents in response to a query.
topic modeling - models for discovering the topics for a set of documents. What are the important documents in a word?
tf-idf
term frequency - number of times a term appears in a document.
function words - words that have little meaning on their own, but are used to grammatically connect other words. E.g.: am, by do, is , which, with, yet...
.
content words - words that carry meaning independently. E.g.: algorithm, category, computer, ...
inverse document frequency - measure of how common or rare a word is across documents. Form: log(totalNumberOfDocuments/numberOfDocumentsContaining(word))
.
tf-idf - ranking of what are important in a document by multiplying term frequency (TF) by inverse document frequency (IDF).
Semantics
information extraction - the task of extracting knowledge from documents.
WordNet
Word Representation
one-hot representation - representation of meaning as a vector of single 1, and with other values as 0.
distributed representation - representation of meaning distributed across multiple values.
You shall know a word by the company it keeps – J.R. Firth, 1957
word2vec - model for generating word vectors
skip-gram architecture - neural network architecture for predicting context words giving a target word.


- Father Gary is coming to preach at St. Paul's on January 21st.
- Our annual congregational meeting will be held on January 28th immediately following worship. It will include an update from the Future Building Committee.
- Large-print bulletins and a hearing loop are available for worship.


Thank you for your interest in customising The Guardian Today
This feature is not yet available as we are still testing demand for it. Tell us your email address and we’ll let you know when it is available (we won’t use it for any other purposes).
@(surveyPage: Page)(implicit request: RequestHeader) @import model.Page @import conf.Configuration.Survey.formStackAccountName @surveyMain(surveyPage) {
This feature is not yet available as we are still testing demand for it. Tell us your email address and we’ll let you know when it is available (we won’t use it for any other purposes).


|
Deuersprech-Kompilierer
Der originale Deuersprech-Kompilierer
|
Öffentliche Methoden | |
| terminal (String nm, String tp) | |
| terminal (String nm) | |
| boolean | is_non_term () |
| String | toString () |
| String | name () |
| String | stack_type () |
| int | use_count () |
| void | note_use () |
| int | index () |
Öffentliche, statische Methoden | |
| static Enumeration | all () |
| static terminal | find (String with_name) |
| static terminal | find (int indx) |
| static int | number () |
Statische öffentliche Attribute | |
| static final terminal | EOF = new terminal("EOF") |
| static final terminal | error = new terminal("error") |
Geschützte Attribute | |
| String | _name |
| String | _stack_type |
| int | _use_count = 0 |
| int | _index |
Statische, geschützte Attribute | |
| static Hashtable | _all = new Hashtable() |
| static Hashtable | _all_by_index = new Hashtable() |
| static int | next_index = 0 |
This class represents a terminal symbol in the grammar. Each terminal has a textual name, an index, and a string which indicates the type of object it will be implemented with at runtime (i.e. the class of object that will be returned by the scanner and pushed on the parse stack to represent it).
|
inline |
Full constructor.
| nm | the name of the terminal. |
| tp | the type of the terminal. |
|
inline |
Constructor with default type.
| nm | the name of the terminal. |
|
inlinestatic |
Access to all terminals.
|
inlinestatic |
Lookup a terminal by index.
|
inlinestatic |
Lookup a terminal by name string.
|
inlineinherited |
Index of this symbol (terminal or non terminal) in the parse tables. Note: indexes are unique among terminals and unique among non terminals, however, a terminal may have the same index as a non-terminal, etc.
|
inline |
Report this symbol as not being a non-terminal.
Erneute Implementation von java_cup.symbol.
|
inlineinherited |
String for the human readable name of the symbol.
|
inlineinherited |
Increment the use count.
|
inlinestatic |
Total number of terminals.
|
inlineinherited |
String for the type of object used for the symbol on the parse stack.
|
inline |
Convert to a string.
Erneute Implementation von java_cup.symbol.
|
inlineinherited |
Count of how many times the symbol appears in productions.
|
staticprotected |
Table of all terminals. Elements are stored using name strings as the key
|
staticprotected |
Table of all terminals indexed by their index number.
|
protectedinherited |
Index of this symbol (terminal or non terminal) in the parse tables. Note: indexes are unique among terminals and unique among non terminals, however, a terminal may have the same index as a non-terminal, etc.
|
protectedinherited |
String for the human readable name of the symbol.
|
protectedinherited |
String for the type of object used for the symbol on the parse stack.
|
protectedinherited |
Count of how many times the symbol appears in productions.
Special terminal for end of input.
special terminal used for error recovery
|
staticprotected |
Static counter to assign unique index.


is an NES emulator.
Currently, it is only supported for mobile devices.
However, if you still want to play, or if you believe you have gotten to this screen on accident, click here.
webNES was originally built at PennApps Spring 2014 by @conradev, @jawerty, @bogidon and @elklein96. It was updated by @memtris. webNES is based off of jsNES, made by @bfirsh.


--- layout: post title: Earth date: '2005-08-01T12:00:00-04:00' tags: - '2005' tumblr_url: http://poetry.liabogoev.com/post/1412794676/earth ---
Turning, turning round.
Our home, our ground,
The Earth, it’s called,
But that’s just a little piece,
We can never see it whole,
Never see both poles,
Our home, our Earth,
It’s weight in gold
it’s worth.