Sketching a parabola

My son has homework (algebra class). Given a problem like this:

y = -(3/2)x2 - 12x - 25

he is supposed to find 5 points on the curve and plot them, and then sketch the curve. Well, actually the software (ALEKS) will plot the curve.

We could use the quadratic equation (my post here) to find the x-intercepts, where

y = 0

And in algebra class they are taught (though not shown why) the axis of symmetry of the parabola is

x = -b/2a

You can derive this as perhaps the most elementary result in calculus:

y = ax2 + bx + c y' = 2ax + b

for a minimum or a maximum the slope is zero:

y' = 0 = 2ax + b x = -b/2a

Or you can complete the square:

y = ax2 + bx + c y/a - c/a = x2 + (b/a)x y/a - c/a + (b/2a)2 = = x2 + (b/a)x + (b/2a)2 = (x + b/2a)2

and recognize that the maximum (or minimum) for y will come when this squared term in x is equal to zero.

However, the problem requires getting 5 points and we only have 3. We remember (or are clued by the word "symmetry" above) and recognize that, if we define x0 as the x at the min/max (equal to -b/2a):

y(x0 + n) = y(x0 - n)

so we really need only one y.

Still, it occurs to me that y(x0 + 1) ought to be simple. We ought not to have to calculate the whole ax2 + bx + c (with those stupid fractions)..

And I wonder what this looks like:

y(x1) = y(-b/2a + 1) = ? y(x2) = y(-b/2a + 2) = ? etc..

It turns out to be extremely simple! Let's call y0 the y when x is on the axis of symmetry (the minimum or maximum), and y1 is when x = x0 +/- 1. We have

y = ax2 + bx + c y0 = a(-b/2a)2 + b(-b/2a) + c = b2/4a - b2/2a + c

We could simplify that, but wait..

y1 = a(-b/2a + 1)2 + b(-b/2a + 1) + c

If you'll let me I'll do the square and multiply by a:

y1 = b2/4a - b + a - b2/2a + b + c

And the difference in y is (since everything in y0 cancels):

y1 = b2/4a - b + a - b2/2a + b + c y0 = b2/4a - b2/2a + c Δy = y1 - y0 = a

Wow! But wait, x0 + 2 is also easy:

y2 = a(-b/2a + 2)2 + b(-b/2a + 2) + c = b2/4a - 2b + 4a - b2/2a + 2b + c Δy = 4a

Let's check with the values given for the problem:

y = -(3/2)x2 - 12x - 25 x0 = -b/(2a) = 12/(-3) = -4 y0 = -24 + 48 -25 = -1

So if x1 = -3 (or -5) then y1 should be equal to

y0 + a = -1 - 3/2 = -5/2

Try x = -3 in the original equation:

-27/2 + 36 -25 = -5/2 check

And if x2 = -2 (or -6) then y2 should be equal to

y0 + 4a = -1 - 6 = -7.

Try x = -2 in the original equation:

-6 + 24 - 25 = -7 check

How cool is that! I'll leave it as an exercise for the reader to show that:

Δy = (Δx)2a

[ UPDATE: I guess I never really appreciated that since we can complete the square to make any linear term in x go away, what we are left with is something of the form (y - y0) = a(x - x0)2.

y = ax2 + bx + c Complete the square: y/a - c/a = x2 + (b/a)x y/a - c/a + (b/2a)2 = = x2 + (b/a)x + (b/2a)2 = (x + b/2a)2 y - c + b2/4a = a(x + b/2a)2

Define

y0 = c - b2/4a x0 = -b/2a (y - y0) = a(x - x0)2

So this is just

y = ax2

with its vertex moved to the point (x0, y0). It's easy to confirm that x = x0 is on the axis of symmetry and thtat (x0, y0) is a solution of the original equation.

Secure communications (3)

This is the third post in a series about remote login using ssh under OS X. The first two posts are here and here. This one is working through the details of the server/client setup using RSA, as described in this O'Reilly article (here, printable). The article also has a link to a page for online testing (of your security setup) by Symantec.

I don't normally bother to remind you that (as it says in the profile) YMMV---your mileage may vary. If you follow the notes here that I describe what I did, and your computer is reduced to a smoking heap of twisted metal in under 10 seconds, well, all I can do is to repeat myself: YMMV. So be careful.

For the server, we first need to set up a directory for keyfiles:

mkdir ~/.ssh

We also need to turn on remote login:

System Prefs > Sharing > Remote login

I always have everything locked down (nothing selected under Sharing) but for today we'll turn on the lights and the stereo. In the middle of the System Prefs window it will say something like "to log in to this computer remotely type":

ssh username@ipaddress

where ipaddress is something like 10.0.X.X. The default SSH port is port 22, which will be unblocked through the firewall automatically after you do this. Now, if you are on the same subnet as the server, from a second machine (say, my laptop) you can do:

ssh username@ipaddress The authenticity of host '10.0.X.X (10.0.X.X)' can't be established. RSA key fingerprint is [ 32 hexadecimal digits ]

This is not the key itself, but its fingerprint, which is much more readable and sufficient for verifying that it is the correct value.

Continues:

Are you sure you want to continue connecting (yes/no)? yes Warning: Permanently added '10.0.X.X' (RSA) to the list of known hosts. Password: Last login: Sat Feb 5 15:19:19 2011 >

At the point where I typed yes, we were about to log in remotely. However, we could be fooled by a malicious evesdropper. At that point, we need to go to the server and do:

ssh-keygen -l -f /private/etc/ssh_host_rsa_key.pub

This will echo the public key for the server, and you should confirm that it matches what you got from ssh above. And if you look on the client (in a second Terminal window) in ~/.ssh:

> cat ~/.ssh/known_hosts 10.0.X.X ssh-rsa __ [ the same server public RSA key ]

To quote the article:

You normally should not see this message again since SSH has written down the key it asked you to check as a "trusted" key for future reference. If you see it again this may mean that someone is impersonating your server. You should immediately disconnect your computer, pick up your phone, and call your network administrator.

From the logged in client enter:

> say I sure love being inside this fancy computer

and hear the message on the server. The default is not Victoria any longer (for that add the option -v Victoria). Our log in currently uses password authentication, but we should really use something more secure. On the client do:

> ssh-keygen -b 1024 -t dsa Generating public/private dsa key pair. Enter file in which to save the key (/Users/telliott/.ssh/id_dsa):

Hit return to choose the default. It will prompt for a password---use a strong password. Then, you will get something like this:

Your identification has been saved in /Users/telliott/.ssh/id_dsa. Your public key has been saved in /Users/telliott/.ssh/id_dsa.pub. The key fingerprint is: [ 32 hexadecimal digits ] telliott@localhost.local The key's randomart image is:

I won't show you the image, but it's pretty cool. Having generated a DSA (cousin of RSA) key pair, we copy our public key over to the server using a secure copy protocol in the current session (which was started with the log in password):

scp ~/.ssh/id_dsa.pub username@serverip:~/.ssh/authorized_keys The server wants a password (the account log in password) and outputs: Password: id_dsa.pub 100% 620 0.6KB/s 00:00 >

Test login by quitting Terminal and restarting, then do:

> ssh username@ipaddress Identity added: /Users/telliott/.ssh/id_dsa (/Users/telliott/.ssh/id_dsa) Last login: Sat Feb 5 15:27:51 2011 from 10.0.X.X >

It works! At this point it would be a good idea to disable automatic login on startup for your client laptop. If a black hat has access to this machine, (s)he could also easily compromise (at least) your account on the server.

Another thing is that if you fail to authenticate by the key (above) the SSH server will fall back on password authentication. We need to edit a file on the server to disable that service. In fact, I recommend turning off Remote Login until we figure that out.

Secure communications (2)

The wikipedia article has a worked example of RSA. I'm going to shamelessly appropriate it for the following discussion.

Choose p = 61 and q = 53 Compute n = pq = 3233 Compute φ(n) = (p-1)(q-1) = 60 times 52 = 3120 Choose a number 1 < e < 3120 that is coprime to 3120

Coprime (or relatively prime) means that e and 3120 should have no common (positive) factor other than 1. Let's try e = 17. Since e is prime, we just have to check that e does not divide 3120 exactly.

>>> 17 * 183 3111 >>> 17 * 184 3128 >>> 3120 % 17 9

e is called the public key exponent.

So the public key would be (n = 3233, e = 17). The encryption function is

m**17 (mod 3233)

The plaintext message would be padded first with extra bits. Now, suppose we want to encrypt the message m = 65. In Python we do m**e % n:

>>> (65**17) % 3233 2790L

Our ciphertext is 2790.

We compute the private key exponent, d, as the modular multiplicative inverse of e (mod φ(n)).

Consider an integer a. The modular multiplicative inverse of a is designated a^-1 where

a a-1 = 1 (mod m)

Here then, we want d such that d * e = 1 (mod 3120). There is an algorithm called the extended Euclidean algorithm to do this. Here we simply note that d = 2753 is a solution since:

>>> (2753 * 17) % 3120 1

Note that the calculation required (effective) knowledge of p and q through the use of φ(n).

In order to decrypt the ciphertext 2790, we do c**d % n:

m = (c**2753) % 3233 (2790**2753) % 3233 65L

That is some serious exponentiation.

From the terminal I do:

> ssh-keygen

The file has this:

ssh-rsa AAAAB3NzaC1yc2EAAAAB..

I'm very surpised to see that this is like ascii alphanumeric or something. I'll have to look into that.

[ UPDATE: it is base 64 (RSA format here), which I'd never heard of but makes a lot of sense: uppercase + lowercase + digits = 62. We just need two more symbols, which are '+' and '/' (here). ]

A key size of 2048 bits would be common for RSA. This would give about a 600 digit number in base 10:

>>> len(str(2**2048)) 617

Not sure what part of that is e versus n, but most of it is probably n, and since pq = n we're talking about quite large prime numbers.

Secure communications (1)

I've been interested in cryptography and the whole question of secure communication over an insecure network, but never had the time to get into it.

I thought we could take a crack at it here. :)

The place to start is public key cryptography. I found a nice (though old) series at O'Reilly on ssh, which includes a very basic description of the cryptography part in the middle of the first article (link / printable). It's written to show Mac users how to use ssh (sorry). There is also a nice and much more extensive article at wikipedia.

As described in the wikipedia article on RSA (an algorithm for public key encryption), there are the following steps:

- choose two distinct large prime numbers p and q about the same size - compute n = pq - compute φ(n) = (p-1)(q-1) - choose e, the public key exponent, e.g. 0x10001 = 65537 - the private key exponent, d, is computed from e and φ(n) - the public key is then (n,e) - the private key is d

The computation to obtain d is described here.

Naturally, the private key is kept secret, while the public key is published.

The important thing is that the encryption and decryption methods have the property that decryption with the private key is the inverse of encryption with the public key:

ciphertext = public key encryption (plaintext)
plaintext = private key decryption (ciphertext)

Even better, the converse is also true:

ciphertext = private key encryption (plaintext)
plaintext = public key decryption (ciphertext)

Thus, Alice can use Bob's public key to encrypt a message that only Bob can decrypt. Bob's problem is that anyone can do this and claim to be Alice, since the encryption used only his public key.

Authentication, or signing, of messages relies on hash functions (like md5). The value computed by md5 from a message (sometimes called a fingerprint) is sensitive to small changes in the message, and also it is "impossible" to fashion a message to match a given hash.

Alice then adopts a modified strategy:

Alice encrypts a message for Bob using his public key Alice uses md5 to compute a hash of the message Alice encrypts the hash using her private key Bob reverses the operations

Only Bob can read the message. He authenticates Alice as the sender because he can decode the hash using her public key and see that it matches what md5 gives him from the message.

The version I've seen of this protocol uses the encrypted version of the message to generate the hash. But I'm not really sure whether you do md5 on the plaintext of the message or the encrypted version, and can't see that it makes a difference as far as Bob is concerned. However, I've also read that an attacker having both plaintext and ciphertext for some message is a weakness, so I think it's better if the hash is of the plaintext for the original message, to protect Alice's private key.

Eve (an evesdropper) cannot read the message, lacking Bob's private key. She cannot substitute a different message of her own, because the hash won't match. She cannot substitute both a different message and a hash, because then when Bob decrypts the hash using Alice's public key, it doesn't match the hash from Eve's message.

There are two more issues to think about right away. The first is that this process is really expensive computationally. So usually, public key cryptography is used to exchange a secret key that is then used for a block or stream cipher.

The second is the question of the validity of public keys. That's the whole purpose of digitally signed certificates (wikipedia).

If you look in the Keychain under Certificates > System Roots, you'll see a (frighteningly long---163 items for me) list of Certificate Authorities whose public key we trust implicitly, and who in turn guarantee say, Bank of America, when you get a logon page for online banking.

But, I'm not so interested in banking. I'm interested in ssh and virtual private networks, and Kerberos.. all sorts of things.

If you know something about this subject (actually the subject of any post) and see an error, or have something to add, feel free to comment.

Lady GaGa---can't get away

You gotta see this. That is all. (here).

Dropbox

Here is some interesting comment on why people like Dropbox.

Like they say---it just works. I've never understood why iDisk sucks so badly (slow, slow, slow...). And I'm allergic to Microsoft, so Windows live or whatever it is was never even considered.

h/t Brad DeLong---just to show I don't hold a grudge. :)

Jake Shimabukuro

wikimedia

I guess I'm probably the last person in the world to learn about this guy:

one
two
three
four
five
my favorite:
six

Incredible feeling...

one more
and the last
but one.
(Can't help myself)

Unix spoken here (4)

There are a just few more Unix commands I should mention before we exhaust everyone's patience. (Three posts here, here, and here).

I'm sure you're familiar with sudo, which stands for superuser, do once. If not, you can see wikipedia. Normally you will use this to write (install) or even delete files in /usr/bin and the like.

> mv /usr/bin/znew ~/Desktop/znew mv: rename /usr/bin/znew to /Users/telliott_admin/Desktop/znew: Permission denied

Don't forget to read the man page on this one. There is always something interesting in the manual.

Many Unix commands appear simple but have numerous options and arguments that make them more like a Swiss Army Knife than a pocketknife. Output on the command line using man can be broken up into chunks or streamed using the down arrow, but maybe you want to study it or keep it as a reference.

For some reason you need to format the output from man in a special way before directing it to a file, for example:

man ls | col -bx > results.txt head -n 8 results.txt .. SYNOPSIS ls [-ABCFGHLOPRSTUW@abcdefghiklmnopqrstuwx1] [file ...]

Nearly the whole alphabet! But doing this without the col leads to selective stuttering:

LS(1) BSD General Commands Manual LS(1) N NA AM ME E l ls s -- list directory contents S SY YN NO OP PS SI IS S l ls s [- -A AB BC CF FG GH HL LO OP PR RS ST TU UW W@ @a ab bc cd de ef fg gh hi ik kl lm mn no op pq qr rs st tu uw wx x1 1] [_ f_ i_ l_ e _ ._ ._ .] D DE ES SC CR RI IP PT TI IO ON N For each operand that names a _ f_ i_ l_ e of a type other than directory, l ls s

head and tail are useful for looking at the first few lines or last few lines of a file. less is like what you get when you just do man some_command ---it gives chunks or streams.

Try man cat to see what else that can do.

There is also split but I couldn't figure out how to make it take my favorite separator ('\n\n').

diff does what you might expect. The use case might be that you have some good edits but also some bad edits to a file, so you want to revert to the old one, and then try the edits one by one.

> diff old.txt new.txt > results.txt > cat results.txt 28a29 > my edit 50,51c51 < < --- > deleted a line here

Or drop results.txt onto TextMate for a little color (graphic).



There's a command to find out information about different processes with finer grained control than Activity Viewer. For example:

ps -u username ps -U userid ps -p processid

Say:

> ps -p 48068 -O %mem PID %MEM TT STAT TIME COMMAND 48068 1.1 ?? S 0:00.91 /Applications/R64.app/Contents/MacOS/R -psn_0_2404939

The man page on ps is extensive.

find is tricky. I need a lot more practice to understand it. Here's a simple one, and then a fun one though:

> find . -name "old.txt" -print ./old.txt > find -f ~/* | wc 118791 235608 11536780

I "find" all the files under my home directory and feed the results to wc (word count), discovering that there are 118,791 lines in the output---that's the number of files! This link seems to have good info on find.

Sometimes I just want to use Python as a calculator or get an ascii value, but without calling up the interpreter (and having to dismiss it):

> python -c 'print 3.0/17' 0.176470588235 > python -c 'print ord("a")' 97 > python -c 'print chr(101)' e > python -c 'import math; print math.e' 2.71828182846

> hexdump -C post.txt 00000000 4d 61 6e 79 20 55 6e 69 78 20 63 6f 6d 6d 61 6e |Many Unix comman| 00000010 64 73 20 61 70 70 65 61 72 20 74 6f 20 62 65 20 |ds appear to be | 00000020 73 69 6d 70 6c 65 20 62 75 74 20 68 61 76 65 20 |simple but have |

Finally, here are a few more that either I've found useful or I'm sure they will be, but I don't feel expert enough to try to explain them. Have fun exploring:

alias awk curl hash md5 openssl sha1 set tar top touch unset

If you get bored here; or try to check out how Greg's email address gets generated!

And there's always ssh. But that really does deserve a post of its own.

Unix spoken here (3)

Let's do some more with Unix commands. Previous posts here and here.

You might have noticed that I have a very short prompt in Terminal, just the character `>` followed by a space. That's because I have an (invisible) file in my home directory named .bash_profile, containing this line:

> cat ~/.bash_profile PS1="> "; export PS1

We can change back to the original behavior by changing the name of the file or moving it, and then re-starting Terminal:

mv ~/.bash_profile ~/Desktop/x.txt

c-98-236-78-154:Desktop telliott$

We could comment out that line of the file (now that it's visible with no leading `.` in the filename, we can easily open it in TextEdit).

#PS1="> "; export PS1

But I like it, so I'll revert to the original situation.

I think there is a way to get TextEdit to show hidden files in the Open dialog, but I forget how at the moment. In any event, it's interesting that having opened and closed the file while it was visible on the Desktop, Open Recent now shows .bash_profile as an option.

Another way to edit the file is to use pico (a command line editor):

> pico ~/.bash_profile

I'm sure you can figure out how to use pico.

One more useful thing in .bash_profile is modification to the $PATH variable. Let's look at that from the command line:

> echo $PATH /opt/local/bin:/opt/local/sbin:/Users/telliott/bin/:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin:/usr/local/ncbi/blast/bin:/usr/texbin:/usr/X11/bin

When I call ls, for example, these directories are searched in turn until the program is discovered finally. It is in:

> whereis ls /bin/ls

If I wanted to modify the $PATH variable I could do:

> PATH=~/Desktop:$PATH; export PATH > echo $PATH /Users/telliott/Desktop:/opt/local/bin:/opt/local/sbin:/Users/telliott/bin/:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin:/usr/local/ncbi/blast/bin:/usr/texbin:/usr/X11/bin

My $PATH is pretty complicated for several reasons: use of MacPorts, some things related to ncbi and X11, etc. It would take too long to explain.

The shell has command history. If you want to repeat a command, just press the up arrow key. To repeat a command further back, keep pushing until you see the one you want. Then press Return. Suppose you have a series of commands (say 3 in a row), and the first of these is 6 commands ago. Press the arrow 6 times, then return. Press the arrow 6 times, then return. Press the arrow 6 times, then return. Because the command history is updated each time, 6 arrow presses gets you back exactly where you need to be for each of the three commands in the sequence.

Alternatively you could do history:

> history 501 cd Desktop 502 pico ~/bash_profile 503 echo $PATH 504 file ls 505 whereis ls 506 PATH=~/Desktop:$PATH; export $PATH 507 PATH=~/Desktop:$PATH; export PATH 508 echo $PATH 509 history

which lists each command I've entered since the last time I booted my machine (even saves between Terminal sessions). One can select a command from the history by number or by partial name match:

> !505 whereis ls /bin/ls > !wh whereis ls /bin/ls

First it prints the command, and then the result. You can combine commands on a single line with `;`

> !504; !512 whereis ls; echo abc /bin/ls abc > history | tail -2 515 whereis ls; echo abc 516 history > !515 whereis ls; echo abc /bin/ls abc

We're getting pretty good with this stuff! We don't really want to list all 500+ commands in the history, just the last two. So we feed the results of history to the Unix tool called tail through a `|`, a Unix "pipe." tail takes an option for how many lines at the end of the "file" to display.

The Unix command grep searches lines of text for those matching a pattern. It's particularly useful in combination with `|`.

> history | grep pico 40 pico ~/.hgrc 298 pico 502 pico ~/bash_profile 515 history | grep pico

Here, I edited some file with pico but I can't remember which one it was. So the entire output of the history is fed through the pipe to grep, searching for lines containing the pattern. Now I can just do:

> !40 pico ~/.hgrc

I won't show you the file.

The last command for this post is ln with the option -s which makes a "soft link" to a file. I can never remember, but you want to put the existing file first (that's the opposite of the way I would design it):

> cat temp/y.txt echo "abc" > ln -s foo temp/y.txt ln: temp/y.txt: File exists > ln -s temp/y.txt foo > ls foo temp > cat foo echo "abc" > ls -l total 8 lrwxr-xr-x 1 telliott staff 10 Jan 31 07:53 foo -> temp/y.txt drwxr-xr-x 5 telliott staff 170 Jan 31 07:53 temp

Now the listing for foo shows an `l` as the first character in the file mode, and it also shows -> temp/y.txt, where it links to.

Unix spoken here (2)

Let's continue with an introduction to Unix commands. First post here. And here are two more good links (one, two).

Let's start by putting some data into a file. We can use the command echo and the `>` redirection operator. Take a look at what's there with cat:

> cd > cd Desktop > echo "abc" > x.txt > cat x.txt abc

Suppose we wish to move this file to a new sub-directory. First we construct the new directory and then we move the file with mv:

> mkdir temp > mv x.txt temp/x.txt > ls temp x.txt > ls temp

Let's make the file `x.txt` actually do something, e.g.:

> echo "echo xyz" > temp/x.txt > cat temp/x.txt echo xyz > sh temp/x.txt xyz

Note that we wrote over the previous contents of temp/x.txt and the file system did not warn us first. There is no way to recover from this if it was a mistake!

The sh command executes the text in the file you give it; in this case the output is familiar. Normally, we'd probably use the file extension .sh for such a script, but it's not required. (Even with Python scripts, the .py extension is only required if you want to import a module).

We can also use the she-bang thing (#!) to make the code in a file executable. Use TextEdit to save the following code in a file y.txt on the Desktop:

#! sh echo abc

Then we do the following. An executable can be executed just by entering its path, but.. there is a restriction that you can't do that for a program in the current directory. You must specify it as the relative path from the directory where we are currently./executable where the `.` means this directory (the restriction has never made a lot of sense to me either, but it's apparently a security hole):

> cat y.txt #! sh echo abc > ./y.txt -bash: ./y.txt: Permission denied

What has happened? We need to make the file "executable" by setting the "permission bits." Without getting into too much detail, these are output using a new option with the ls command:

> ls -l y.txt -rw-r--r-- 1 telliott staff 19 Jan 30 20:08 y.txt > chmod 711 y.txt > ls -l y.txt -rwx--x--x 1 telliott staff 19 Jan 30 20:08 y.txt > ./y.txt abc

The three permissions are r (read), w (write) and x (execute), listed in order for the user, her group, and the world. 7 is all of them. `x` is 1, `w` is 2, `r` is 4, and the combinations result from addition.

There are various shorthands for this. First reverting the previous change, then we could do this:

> chmod 644 y.txt > chmod u+x y.txt > ls -l y.txt -rwxr--r-- 1 telliott staff 19 Jan 30 20:08 y.txt

We have given the user (only) permission to execute the file.

> ls -l ~/Desktop total 1 drwxr-xr-x 2 telliott staff 102 Jan 30 20:08 temp -rw-r--r-- 1 telliott staff 15 Jan 30 20:08 y.txt

When we do ls on the Desktop directory (above), we get a listing for both the temp sub-directory and the file. Note that the first character in the "file mode" is d for the directory. staff is my group name, and after that comes the number of bytes in each "file", including directories.

From man ls

The Long Format
If the -l option is given, the following informa-
tion is displayed for each file: file mode, num-
ber of links, owner name, group name, number of
bytes in the file, abbreviated month, day-of-
month file was last modified, hour file last mod-
ified, minute file last modified, and the path-
name. In addition, for each directory whose con-
tents are displayed, the total number of 512-byte
blocks used by the files in the directory is dis-
played on a line by itself, immediately before
the information for the files in the directory.
If the file or directory has extended attributes,
the permissions field printed by the -l option is
followed by a '@' character. Otherwise, if the
file or directory has extended security informa-
tion (such as an access control list), the per-
missions field printed by the -l option is fol-
lowed by a '+' character.

And finally, ls also has a recursive option, which can be grouped into -lR:

> ls -lR total 8 drwxr-xr-x 3 telliott_admin staff 102 Jan 31 06:59 temp -rw-r--r-- 1 telliott_admin staff 15 Jan 31 07:00 y.txt ./temp: total 8 -rw-r--r-- 1 telliott_admin staff 4 Jan 31 06:59 x.txt

Let's continue by copying this file into our temp directory:

> cp y.txt temp > ls temp y.txt > ls temp x.txt y.txt

On the other hand, mv actually "moves" the file:

> mv y.txt temp > ls temp > ls temp x.txt y.txt

Once again, note the lack of warnings. The old copies of y.txt on the Desktop (and in temp) are gone forever.

Eventually, we tire of this. First we try to delete a single file:

> rm temp/y.txt > ls temp x.txt

But maybe temp has lots of files, so we try:

> rmdir temp rmdir: temp: Directory not empty > rm -r temp > ls >

The `-r` option is really dangerous. The classic Unix "joke" is to tell someone to do some combination of rm and -r and *. Don't fall for it.

You might think about looking at the man page for rm and maybe using the -i option.

Unix spoken here (1)

There are probably hundreds of pages on the web with good info about basic Unix commands (e.g. here, here). I thought I'd give some of the commands I think are most useful, but I have to start at the beginning. So, here goes with Unix in 5 minutes, Unleashed, For Dummies..

> cd > pwd /Users/telliott > cd Desktop > pwd /Users/telliott/Desktop > cd ~ > pwd /Users/telliott > cd Desktop > ls x.txt > cat x.txt some data

The first command, cd, says to change directory; with no other argument given, we go to our home directory. To see where we are in the file system we can do pwd: print working directory. Also, the ~ symbol is a shorthand for the user's home directory.

The "shell" is smart and has "command-completion." For example, from my home directory I enter cd De and then press tab. The shell fills out "Desktop."

Another very common command is ls: list the contents of the current directory (since there is no argument). And to see the contents of a file you might do cat with the results shown.

> ls -a . .DS_Store .temp .. .localized x.txt > ls /usr/bin/pyth* /usr/bin/python /usr/bin/python2.6-config /usr/bin/python-config /usr/bin/pythonw /usr/bin/python2.5 /usr/bin/pythonw2.5 /usr/bin/python2.5-config /usr/bin/pythonw2.6 /usr/bin/python2.6

Any directory may have "hidden" files whose names are prefaced by a dot `.`. These can be shown with ls -a. There are many (many) other options with results cataloged under man some_command.

The shell understands paths to files in both an absolute and relative sense. A path starting with / is absolute, otherwise it's relative. Hence /usr/bin is a directory starting from the root of the file system, while Desktop is only understood as a valid destination if I'm in my home directory (or some other directory with Desktop as a sub-directory).

The character * is a wild card and matches anything; ls /usr/bin/pyth* lists all the entries matching pyth- + something in the given directory.

> pushd /usr/bin /usr/bin ~/Desktop > pwd /usr/bin > popd ~/Desktop > pwd /Users/telliott/Desktop > cat -n ~/Desktop/x.txt 1 some data > cal January 2011 Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 > cd .. > pwd /Users/telliott_admin

Sometimes we want to make a jump in the file system but intend to come right back. pushd and popd are useful here, with results as shown.

As one more example of using options or arguments to a command, cat takes the option -n, which numbers the output lines. cal is probably faster than finding the Calendar.app, since I don't usually have it in the Dock.

Finally, to move toward the tips of the file system tree, you specify the directory at the next level so it has to be explicit, but there is only one parent, which we can reach implicitly with cd .., meaning "go up."

Distributed Objects on OS X (2)

I struggled for a while to get Distributed Objects working between different machines (first post here for same-machine example). According to the docs and this, you should just use

NSSocketPortNameServer *name_server; name_server = [NSSocketPortNameServer sharedInstance]; NSLog(@"%@", [name_server description]); BOOL result; result = [conn registerName:@"my_server" withNameServer:name_server];

But it didn't work for me. So I asked a question on SO (here), and asked the Google. The latter approach finally worked. I got a working example with code from here. The discussion in the docs for the NSConnection class helped too (see initWithReceivePort:sendPort:. If you set it up with nil for the sendPort, it uses the same port for both sending and receiving, which is what you want.)

[UPDATE: On reflection, it does seem a bit weird, because a Mach port is supposed to be a one-way channel, yet these are clearly two way. I guess they are probably complex objects built from multiple NSMacPorts. ]

Server:

// gcc talk3.m -o test -framework Foundation // http://web.archiveorange.com/archive/v/SEb6a6s543xreqfXtOCQ #import <Foundation/Foundation.h> @interface VendedObject:NSObject {} -(NSString *) speak; @end @implementation VendedObject -(NSString *) speak { return @"woof"; } @end @interface NSConnection (NetworkServiceAdditions) + (id) networkServiceConnectionWithName:(NSString *) inName rootObject:(id) inRootObject; @end @implementation NSConnection (NetworkServiceAdditions) + (id) networkServiceConnectionWithName:(NSString *) inName rootObject:(id) inRootObject; { NSSocketPort *port = [[[NSSocketPort alloc] init] autorelease]; NSConnection *connection = [NSConnection connectionWithReceivePort: port sendPort: nil]; [[NSSocketPortNameServer sharedInstance] registerPort:port name:inName]; [connection setRootObject: inRootObject]; return connection; } @end int main(){ NSAutoreleasePool *pool; pool = [[NSAutoreleasePool alloc] init]; VendedObject *obj; obj = [[[VendedObject alloc ] init] autorelease]; NSLog(@"%@", [obj description]); NSConnection *conn; conn = [NSConnection networkServiceConnectionWithName:@"my_server" rootObject:obj ]; NSSocketPortNameServer *name_server; name_server = [NSSocketPortNameServer sharedInstance]; NSLog(@"%@", [name_server description]); NSLog(@"%@", [name_server portForName:@"my_server"]); [[NSRunLoop mainRunLoop] run]; [pool drain]; return 0; }

Note: if you're not just killing the Server (as I did) you should do invalidate on the connection (and I guess the ports too?).

Client listen.py is on my laptop:

from Foundation import * proxy_obj = NSConnection.rootProxyForConnectionWithRegisteredName_host_usingNameServer_( "my_server", "osxserver.local", NSSocketPortNameServer.sharedInstance()) if not proxy_obj: print 'Did not get an object from the server.' else: print proxy_obj.description() print type(proxy_obj) print proxy_obj.speak()

Output:

> python listen.py <VendedObject: 0x10010ced0> <objective-c class NSDistantObject at 0x7fff70a64868> woof

It works!

NSTask again

I have a bit more to explore about NSTask (previous post here). There is some discussion on SO about the difference between an NSTask and an NSThread (here).

The script task.py uses the #! thing and is set to be executable (by the user only). The code looks for an int in argv and a second arg that tells whether to examine the environment variable dictionary.

#! /usr/bin/python import sys, os try: n = int(sys.argv[1]) except: n = 2 print 'woof ' * n if len(sys.argv) == 3: D = os.environ k = 'MYKEY' if k in D: print k, D[k] else: print k, 'not present'

The first attempt just launches the task without setting it up first.

The second example does the setup. The path p2 (to Python directly) isn't used in these versions but I left it in. For a while, I was getting errors when I tried to setup the task and then launch it unless I fed it to Python first and gave the script path as an argument. Then, the errors just stopped. I can't recreate the problem. This kind of bug that "just disappeared" happened with the environment dictionary as well. No clue as to why.

from Foundation import * p1 = NSHomeDirectory() + '/Desktop/task.py' p2 = '/usr/bin/python' def f1(): t = NSTask.launchedTaskWithLaunchPath_arguments_( p1, [str(1)]) def doit(t): t.launch() t.waitUntilExit() def f2(): t = NSTask.alloc().init() t.setLaunchPath_(p1) doit(t) f1() f2()

Of note here is that the arguments must be in a list or array, and that the int argment must be converted to a string. The error if not is weird (but at least we're pointed to the correct line):

2011-01-29 03:18:00.109 Python[19298:60f] -[OC_PythonNumber fileSystemRepresentation]: unrecognized selector sent to instance 0x101a6d950 Traceback (most recent call last): File "parent.py", line 48, in <module> f() File "parent.py", line 15, in f1 p1, [1]) ValueError: NSInvalidArgumentException - -[OC_PythonNumber fileSystemRepresentation]: unrecognized selector sent to instance 0x101a6d950

Otherwise we get this:

> python parent.py woof woof woof

Next, we instantiate the task and then set its arguments and environment, having modified the dict to have an extra key/value pair:

D = NSProcessInfo.processInfo().environment() D['MYKEY'] = "MYVALUE" def f3(): t = NSTask.alloc().init() t.setLaunchPath_(p2) n = str(3) t.setArguments_([p1,n,'withenviron']) t.setEnvironment_(D) print 'MYKEY', t.environment()['MYKEY'] doit(t) f3()

> python parent.py MYKEY MYVALUE woof woof woof MYKEY MYVALUE

The ultimate line of output is from the task and shows that we did get the modified environment.

And in the last example, we use an NSFileHandle and redirect standard output. This could be useful in the case where you don't have full control over the task that is being executed. I found that NSFileHandle.fileHandleForWritingAtPath_ apparently requires the file to already exist.

p3 = NSHomeDirectory() + '/Desktop/results.txt' def f4(): t = NSTask.alloc().init() t.setLaunchPath_(p1) n = NSNumber.numberWithInt_(4).stringValue() t.setArguments_([n]) # file must exist or this fails! f = NSFileHandle.fileHandleForWritingAtPath_(p3) t.setStandardOutput_(f) doit() data = f.readToEndOfFileInBackgroundAndNotify() print data f4()

> python parent.py None > cat results.txt woof woof woof woof

The redirect is good, but I couldn't get the file read to work. I tried before and after launch, and I tried re-grabbing the file handle, and I also tried readDataToEndOfFile. Not sure what's up with that yet.

[UPDATE: Perhaps the answer has something to do with NSPipe (here). ]

Decorators in Python

There is a nice simple post about Python decorators from Bruce Eckels (here; discussion on Stack Overflow here, docs here, more here). I copied some of his example code and show it below, but first, the output of the run:

> python script.py init init start Entering func1 inside func1() Exited func1 Entering func2 inside func2() Exited func2

The main point is that a decorator is a kind of macro for functions. It changes them, and can do so in almost unlimited ways. The output above shows that the decorator code can be executed before or after the function itself is called. (And he notes that you don't even have to do that!) They're used quite a bit in PyObjC (e.g. @objc.signature('v@0:@8')). I should probably explore all of that in another post.

As Bruce says:

Decorators allow you to inject or modify code in functions or classes

The only constraint upon the object returned by the decorator is that it can be used as a function -- which basically means it must be callable. Thus, any classes we use as decorators must implement __call__.

What should the decorator do? Well, it can do anything but usually you expect the original function code to be used at some point. This is not required, however.

class entryExit(object): def __init__(self, f): print 'init' self.f = f def __call__(self): print "Entering", self.f.__name__ self.f() print "Exited", self.f.__name__ @entryExit def func1(): print "inside func1()" @entryExit def func2(): print "inside func2()" print 'start' func1() func2()

A peek into the Objective-C "runtime"

I'm playing with Cocoa today. I ran across a post (here), reminding me that all our fancy "messages" get changed by the Objective-C "runtime." The real call is objc_msgSend and you can do that yourself if you want:

// gcc test.m -o test -framework Foundation #import <Foundation/Foundation.h> @interface MyClass:NSObject {} -(NSString *) speak:(int) n; @end @implementation MyClass -(NSString *) speak:(int) n { int i; NSMutableArray *mA; mA = [NSMutableArray arrayWithCapacity:n]; for (i=0; i<n; i++) { [mA addObject:@"woof"]; } return [mA componentsJoinedByString:@"-"]; } @end int main(){ NSAutoreleasePool *pool ; pool = [[NSAutoreleasePool alloc] init]; MyClass *obj; obj = [[[MyClass alloc ] init] autorelease]; NSLog(@"%@", [obj description]); NSLog(@"%@", [obj speak:2]); NSString *s; int count = 3; SEL sel = @selector(speak:); s = objc_msgSend(obj,sel,count); NSLog(@"%@", s); [pool drain]; return 0; }

Note: you have to use an int variable, you can't just pass an int directly to objc_msgSend.
Output:

> ./test 2011-01-27 13:21:37.890 test[38774:903] <MyClass: 0x10010cd20> 2011-01-27 13:21:37.892 test[38774:903] woof-woof 2011-01-27 13:21:37.893 test[38774:903] woof-woof-woof

Distributed Objects on OS X

I got a simple example with Distributed Objects working. This is supposed to be the standard way to communicate between processes. I tried it first with both the Server and the Client in PyObjC. Eventually I rewrote the Server in Objective-C and then it worked.

[UPDATE: Found a great working example (old, but from an Apple engineer here). ]

The output is:

> python listen.py <VendedObject: 0x10010cce0> <objective-c class NSDistantObject at 0x7fff70a64868> woof

I'm not sure what the problem was but the error I got was

[OC_PythonString initWithBytes:length:encoding:]: unrecognized selector sent to instance 0x3635130

Server:

// gcc talk.m -o test -framework Foundation #import <Foundation/Foundation.h> @interface VendedObject:NSObject {} -(NSString *) speak; @end @implementation VendedObject -(NSString *) speak { return @"woof"; } @end int main(){ NSAutoreleasePool *pool; pool = [[NSAutoreleasePool alloc] init]; VendedObject *obj; obj = [[[VendedObject alloc ] init] autorelease]; NSLog(@"%@", [obj description]); NSConnection *conn; conn = [[[NSConnection alloc] init] autorelease]; [conn setRootObject:obj]; BOOL result; result = [conn registerName:@"my_server"]; if (!result) { NSLog(@"Failed to register Name"); } else { NSLog(@"%@", [conn description]); } [[NSRunLoop mainRunLoop] run]; [pool drain]; return 0; }

Run with:

> ./test 2011-01-27 12:09:39.001 test[36995:903] <VendedObject: 0x10010cce0> 2011-01-27 12:09:39.005 test[36995:903] (** NSConnection 0x100112050 receivePort <NSMachPort: 0x100112530> sendPort <NSMachPort: 0x100112530> refCount 1 **)

You'll have to kill the process when you're done. If you have tried once already in Terminal, you will need to Quit Terminal and Re-launch. Otherwise registerName: will fail.

Client:

from Foundation import * proxy_obj = NSConnection.rootProxyForConnectionWithRegisteredName_host_( #"my_server", "osxserver.local") "my_server", None) if not proxy_obj: print 'Did not get an object from the server.' else: print proxy_obj.description() print type(proxy_obj) print proxy_obj.speak()

I also tried to connect to another machine on my local network, but I couldn't get that to work either. The proxy_obj was nil/None.

NSNotifications

I want to send information between two running applications and I mistakenly thought I could use an NSNotification to do this. [See the UPDATE].

So this post is about the first step, getting an NSNotification to work within a running app. The following is from an Xcode Cocoa-Python app, and in AppDelegate.py we have:

from Foundation import * from AppKit import * import objc class SpeakAppDelegate(NSObject): def applicationDidFinishLaunching_(self, sender): NSLog("Application really did finish launching.") nc = NSNotificationCenter.defaultCenter() nc.addObserver_selector_name_object_( self, "mycallback:", 'love_note', None) @objc.signature('v@0:@8') def mycallback_(self,note): print 'note' print note.description() @objc.IBAction def button_(self,sender): print sender, 'button' nc = NSNotificationCenter.defaultCenter() nc.postNotificationName_object_userInfo_( 'love_note', None, {'path':'xyz'})

There's a button in the window hooked up to the IBAction. I push the button and get:

<NSButton: 0x61c7b0> button note NSConcreteNotification 0x6337a0 {name = love_note; userInfo = { path = xyz; }}

But I couldn't get it to work between apps, for example with this one compiled in Terminal:

// gcc tell.m -o test -framework Foundation #import <Foundation/Foundation.h> int main() { NSNotificationCenter *nc; nc = [NSNotificationCenter defaultCenter]; [nc postNotificationName:@"love_note" object:nil userInfo:nil ]; return 0; }

I asked on Stack Overflow (here), and they say I should be using Distributed Objects (here). So I have to look into that.

[ UPDATE: Just substitute NSDistributedNotificationCenter in the code above. It works! ]

Nullspace of a vector

This post is a note to myself about linear algebra.

Let's consider two vectors in R²:

a = ( 3, 4) = [ 3 ] [ 4 ] b = (-3, 1) = [ -3 ] [ 1 ]

We can see from a plot that these vectors a and b are obviously not pointing in the same direction.



Also we notice that a is not a multiple (or a linear combination) of b (or vice versa). There is no constant such that when the elements of a are multiplied by the constant we get b.

Now consider a point P in R², say

P = (2,-4)

We can construct a linear combination of a and b that reaches this P or any other point.

How? Simply place one of the vectors at the origin and move along it (perhaps in a negative direction), and place the second vector at P and move along it, and find where the two lines meet.



Call the coordinates of the point where the lines cross x and y. There are actually two possibilities depending on which vector we choose for each role. Suppose we move in the reverse direction from the origin along a and from P along b. From the point-slope equation we know that:

(0 - y) / ( 0 - x) = 4/3 (from a) (Py - y) / (Px - x) = -1/3 (from b) (-4 - y) / ( 2 - x) = -1/3

We can solve these two equations pretty easily. From the first

y = 4/3 x

and from the second:

(-12 - 3y) = -(2 - x) x = -10 - 3y = -10 - 3(4/3) x 5x = -10 x = -2 y = -8/3

The other solution is symmetrical (we're dealing with a parallelogram). We would need to go +2 across and +8/3 up from P to reach x, y = (4, -4/3).

Suppose we want to know the actual multipliers for a and b, i.e. the fraction of the length of a and b that we travel along each vector.

From the figure, we can estimate that the values will be about -0.7 and -1.25.



Call these multipliers u and v. In matrix language

M = [ 3 -3 ] [ 4 1 ] [ 3 -3 ] [ u ] = [ 2 ] [ 4 1 ] [ v ] [ -4 ]

One way we can solve the system (call it the Algebra 2 way) is as follows:

3u - 3v = 2 4u + v = -4

Solve the second equation for v:

v = -4u - 4

Plug into the first equation:

3u - 3(-4u - 4) = 2 15u = -10 u = -2/3 v = 8/3 - 4 = -4/3

Finally, consider P not just as a point but as a vector c:

a = ( 3, 4) b = (-3, 1) c = ( 2,-4)

Since we could have chosen P to be any point, c could be any vector in the x,y-plane and it would be constructed as a linear combination of a and b:

u a + v b

We say that c is in the column space of the matrix whose columns are the vectors a and b:

M = [ 3 -3 ] [ 4 1 ]

because we can get to c by taking a linear combination of the columns of M.

And of course, having a + b = c, we can also add -c to get:

u a + v b - c = 0

If we think of another matrix as the column vectors a, b and c lined up:

[ 3 -3 2 ] [ u ] = [ 0 ] [ 4 1 -4 ] [ v ] = [ 0 ] [ w ] = [ 0 ]

The combination u = -2/3, v = -4/3, w = -1 solves this equation and brings us back to zero:

-2/3 [ 3 ] -4/3 [ -3 ] - [ 2 ] = [ 0 ] [ 4 ] [ 1 ] [ -4 ] [ 0 ] [ -2 ] + [ 4 ] + [ -2 ] = [ 0 ] [ -8/3 ] [ -4/3 ] [ 4 ] [ 0 ]

That solution (a vector in R³):

x = [ u ] = [ -2/3 ] [ v ] [ -4/3 ] [ w ] [ -1 ]

is said to be in the nullspace of

A = [ 3 -3 2 ] [ 4 1 -4 ]

because Ax = 0.

Sal Khan rocks

I'm always the last person to learn about cool new stuff, so when I say I was scouting around on the web today and ran into Sal Khan and his Khanacademy, I expect you will say, I know about him already. I mean, it's 10,000,000 downloads and counting, or something.

If you don't know, the site consists of a very large number of videos on math, science, economics and a few other topics (here). Since Sal's been interviewed a lot, if I still watched PBS reliably, I would've known about him already. But I decided a while ago to watch as little TV as possible.

Several things to say about the material:

(1) the scope is incredible
(2) the depth is also incredible
(3) the quality is excellent

I'm using it to flesh out what I'm getting from Gil Strang on Linear Algebra.

He also seems to be a really nice guy. Check it out!

NSCountedSet

I just got a helpful comment on an old post (here) suggesting the use of an NSCountedSet. I'd never heard of this class, but it's described in the Apple docs about Collections (here). Besides the usual characters

NSArray NSMutableArray NSDictionary NSMutableDictionary NSIndexSet

there are several others including:

NSPointerArray NSPointerFunctions NSMapTable NSHashTable NSCountedSet

Let's show off the last one, from PyObjC. Here's the listing:

from Foundation import * L = list('xyyzzz') S = NSCountedSet.alloc().initWithArray_(L) def show(S): e = S.objectEnumerator() while True: obj = e.nextObject() if not obj: break print obj, S.countForObject_(obj) print show(S) N = S.countForObject_('z') for i in range(N): S.removeObject_('z') print 'z', S.countForObject_('z') print 'w', S.countForObject_('w')

and the output:

x 1 y 2 z 3 z 2 z 1 z 0 w 0

It feels a bit strange, not only can you get the count of an object that's not in the set (as in Python), but as the docs say:

removeObject: does nothing if anObject is not present in the set