\documentclass[12pt]{article}
\usepackage{psfig}
\usepackage{amsfonts, amssymb, amsmath, amscd, framed}
\usepackage{listings}

\usepackage{color}
\usepackage{textcomp}
\definecolor{listinggray}{gray}{0.9}
\definecolor{lbcolor}{rgb}{0.9,0.9,0.9}

\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{observation}{Observation}

\newenvironment{proof}{\noindent{\bf Proof:} \hspace*{1em}}{
        \hspace*{\fill} $\triangle$ }

\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\backtick}{{\texttt{\char"12}}}

\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}

\newcommand{\htitle}[3]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}
{Q for smarties \cite{shasha}
\hfill #1 \newline
Pune\hfill#3\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf #2}\end{center}}

\newcommand{\handout}[3]{\thispagestyle{empty}
 \markboth{ #2}{ #2}
 \pagestyle{myheadings}\htitle{\protect\ref{#1}}{#2}{#3}}


\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

%\lstset{ %
%	language=Perl,                % the language of the code
%	basicstyle=\footnotesize,       % the size of the fonts that are used for the code
%	%numbers=left,                   % where to put the line-numbers
%	numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
%	stepnumber=1,                   % the step between two line-numbers. If it's 1, each line 
					% will be numbered
%	numbersep=1pt,                  % how far the line-numbers are from the code
	%backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
%	showspaces=false,               % show spaces adding particular underscores
%	showstringspaces=false,         % underline spaces within strings
%	showtabs=false,                 % show tabs within strings adding particular underscores
%	frame=single,                   % adds a frame around the code
%	tabsize=2,                      % sets default tabsize to 2 spaces
%	captionpos=b,                   % sets the caption-position to bottom
%	breaklines=true,                % sets automatic line breaking
%	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
%	title=\lstname,                 % show the filename of files included with \lstinputlisting;
%					% also try caption instead of title
%	escapeinside={\%*}{*)},         % if you want to add a comment within your code
%	morekeywords={*,`,...}            % if you want to add more keywords to the set
%}
\lstset{ %http://www.tjansson.dk/?p=419
	backgroundcolor=\color{lbcolor},
	tabsize=4,
	rulecolor=,
	language=q,
        basicstyle=\small,
        upquote=false;
        aboveskip={1.5\baselineskip},
        columns=fixed,
        showstringspaces=false,
        extendedchars=true,
        breaklines=true,
        prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
        frame=single,
        showtabs=false,
        showspaces=false,
        showstringspaces=false,
        identifierstyle=\ttfamily,
        keywordstyle=\color[rgb]{0,0,1},
        commentstyle=\color[rgb]{0.133,0.545,0.133},
        stringstyle=\color[rgb]{0.627,0.126,0.941},
}
\begin{document}
\htitle{Professor Dennis Shasha}{q for smarties 1}{2011} 
\paragraph{Introduction} 
Q is a successor to k which is a successor to A+, an APL
successor. 
Arthur Whitney, the designer and implementor believes
in concise, expressive, and efficient languages.
In fact, q is implemented on top of k.
The executable is under 400 kilobytes.

Some people like to develop directly in the interpreter.
I tend to develop programs in files and then execute them.

The basic data types are atoms (single entities, e.g. a single number),
lists (a sequence of atoms) which double as arrays, dictionaries, and tables.
The language is very powerful: you can do bulk operators on entire
arrays and tables and do interprocess communication.
If treated well, it can also execute fast.

Operators (sometimes called "verbs") can operate on any data type
but in different ways. 
A good way to get familiar with the language is to type

\begin{lstlisting}
\l help.q
\end{lstlisting}

in a q window

\begin{lstlisting}
q) help ` /this is a backtick not single quote. TBD 
q) help `verbs /this is a backtick and not single quote. FIXME
\end{lstlisting}

Let's start off simple:

\begin{lstlisting}

q) x: 4 

q) y: 5

q) x+y

q) x * y

q) x: 4 40 400 

q) y: 5 55 80

q) x + y

q) x * y
\end{lstlisting}
\vspace{30mm}
Note however that processing goes from right to left rather than
through operator precedence.
So, for example, what do you anticipate you would get from:

\begin{lstlisting}
5 - 4 * 3

5 * 4 - 3

(5 * 4) - 3

\end{lstlisting}

\begin{lstlisting}
sum x * y / ability to "compose" functions

x[1]

y[2]

z: ((1 2 3);(4 5 6);(7 8 9 10))

z[1;2]

z[1 2] 

\end{lstlisting}

Some useful monadic (single argument) verbs: \cite{kxref}

\begin{lstlisting}
til 10
1 + til 10
x: 1 + til 10
y: 3 + til 10
reverse x


v: 3 2 6 4 9 8 6 5 2 3 4
distinct v
first v
min v
max v
sum v
sums v
prd v
prds v
count v
iasc v / permutation that will give sorted array
v[iasc v] / sorted array itself
avg v

\end{lstlisting}
\vspace{20mm}
Please take time tonight to review all the commands
in basicmoves.q

\lstinputlisting[language=q,firstline=0,lastline=174]{basicmoves.q}
\vspace{40mm}
Now let's put some commands inside a file and execute them 
based on their command-line arguments.

Call the file findcount.q\\
The ``I"\$ means that the arguments should be integers.\\
The arguments are on the command line and are copied to .z.x\\
findcount.q:
\lstinputlisting[language=q,firstline=0,lastline=17]{findcount.q}
\begin{lstlisting}
q findcount.q 2 3 42 11 1
\end{lstlisting}
\begin{framed}
Exercise 1: Create a file that produces the arithmetic mean of 
the arguments on the command line.
        q findmean.q 2 1 4 0 9
\end{framed}
A few dyadic (dual argument) verbs.
\begin{lstlisting}
x + y
x * y
x % y  / notice that division is %, because the / is used for comments and more
\end{lstlisting}
Now, we can start writing procedures to do things.
For example, let us write a procedure to project the medicare budget
into the future.
We have to know the current level, the percent raise, and 
the number of years.
Then we can write a procedure that will give us the budget
after so many years.

\begin{lstlisting}
project:{[current; interest; numyears]
 x: (1 + interest) xexp numyears;
 x * current}

/ 2010 medicare budget is about $453
/ So projected budget in  2030 will be:
project[453; 0.03; 20]
\end{lstlisting}
\vspace{30mm}
See budget.q:
\lstinputlisting[language=q,firstline=0,lastline=13]{budget.q}

Note a few things:\\
Need a semi-colon after every line but the last one. (Forgetting this can lead to strange bugs.)\\
Every line except the function definition should be outdented.

Now compute into the future and see what the budget will be.

The present value of an income stream given an annual interest rate
is the sum of the contribution from year 1, year 2, ...
To compute the contribution from year k, you have to take the amount
you receive in year k and find the amount you would have to deposit
now in order to get that amount k years from now.
\begin{framed}
Exercise 2: Create a file that produces the present value
of a sequence of floating point numbers given as payments
for year 1, year 2, ... up to the length of the vector.
Hint: prds and \# may help.
Hint: try 10 \# 0.3
\begin{lstlisting}
        q presval.q 100 200 100 400
\end{lstlisting}
\end{framed}
Suppose you want to compute certain summary statistics of a
collection of numbers.
For example, if the original sample is 
\begin{lstlisting}
x: 10 ? 5

x
\end{lstlisting}
You might get a mean of:
\begin{lstlisting}
avg x
\end{lstlisting}
but the numbers are jumping around much more than if you have 
\begin{lstlisting}
1.9 + 10 ? 0.2
\end{lstlisting}
Under the normal distribution assumption, we would compute a 
standard deviation. 

\begin{lstlisting}
sqrt var x
\end{lstlisting}
But what if we don't care to assume
a normal distribution (because we think the data could have a bias).
In resampling statistics, you don't assume a distribution.
Instead you take the data as it is and take repeated samples
of the same size "with uniform probability at random using replacement".
What this means is that we might create samples like this:
\begin{lstlisting}
x[(count x) ? count x]
\end{lstlisting}
and again
\begin{lstlisting}
x[(count x) ? count x]
\end{lstlisting}
and again
\begin{lstlisting}
x[(count x) ? count x]
\end{lstlisting}
That is, you might create such samples 10,000 times and then
store all the means.
If you then sort all the means and take the 250th and the 9,750th
you have the limits of the 95\% confidence interval.

To do this, you'll need to understand two constructs:
to append to a list, you can do something like:
\begin{lstlisting}
mylist: x[10 ? count x]
mylist,: x[10 ? count x]
\end{lstlisting}
To iterate, you can use a loop such as:

\begin{lstlisting}
mylist: ();
do[10000; mylist,: avg x[(count x) ? count x]]
\end{lstlisting}
\begin{framed}
Exercise 3: Given a list of integers at the command line,
compute the mean, 2.5\% value and 97.5\% value using resampling.
\end{framed}
Ok, now continuing our discussion of resampling statistics,
let us say that we have two lists and we want to compute the 
significance of the difference of two means.
A classical application is drug testing.
We test the drug vs. the placebo.
The way we do this is again by resampling.
We take the two lists, compute the mean difference
and then see whether permuting the labels would give us the same
difference or more. 
We do this many times and determine what fraction of the time
random permutation gives a bigger difference.
Whenever random permutation gives a bigger difference,
we ascribe the difference to chance.

For example, if we have

\begin{lstlisting}
drug: 50 + 20 ? 15
placebo: 30 + 30 ? 30
\end{lstlisting}
then we get an initial difference of means of

\begin{lstlisting}
(avg drug) - (avg placebo)
\end{lstlisting}
To see how often this would happen if we permuted the labels,
we take the whole vector


\begin{lstlisting}
v: drug,placebo
\end{lstlisting}
and permute it 10,000 times.
After each permutation,
we take the average value of  the first (in this case) 15 elements
and the next 30.
We count how often the computed average is greater than 
or equal to the measured average.
That count divided by 10,000 is the $p-value$.
(p-value = probability that the observed difference in the mean
happened by chance.)

\begin{framed}
Exercise 4a: Given two lists drug and placebo, find the $p-value$
of the difference in their means. \\
\begin{lstlisting}
  q evalsig.q 4 5 2 3 5 1 _ 1 2 3 1 2 1 
\end{lstlisting}
\end{framed}

\begin{framed}
Exercise 4b (easier than 4a):
The present interest rate is 5\%.
Over each of the next five years (including the first year),
the interest rate can go up
by 0.5\%, down by 0.5\%, or stay the same, all with the same
probability.
Find the median net 5 year interest rate, as well as the 75th
and 25th percentiles.

\begin{lstlisting}
        q montecarlo.q 5 0.5
\end{lstlisting}
\end{framed}
\begin{framed}
Exercise 4c (harder than 4b)
Allow the number of years, the present interest rate and the 
increment of the interest rate to be variable.
Find the median net $n$ year interest rate, as well as the 75th
and 25th percentiles.
\end{framed}
Switching gears a little and recognizing that finance is a lot about time,
let's learn a little about date arithmetic.
First, there is a date $data type$:

\begin{lstlisting}
mystart: "D"$(string 2030),(".01.01")
myend: "D"$(string 2030),(".12.31")

`week$ mystart / finds  the date of the monday just prior or equal to mystart
`week$ myend
\end{lstlisting}
To find the day of the week of mystart.
\begin{lstlisting}
finddayofweek:{[x] 
  numdays: x - `week$ x;
  vec:`mon`tues`wed`thurs`fri`sat`sun;
  vec[numdays]}

finddayofweek[mystart]
\end{lstlisting}

\begin{framed}
Exercise 5:
Find all the weekend dates of a given year where the year is given 
as a command line argument.
\begin{lstlisting}
        q findweekend.q 2020
\end{lstlisting}
\end{framed}


\begin{framed}
Exercise 5b: Find all third Saturdays in every month
for a given year.
\begin{lstlisting}
        q findthirdsat.q 2025
\end{lstlisting}
\end{framed}

Q can also handle strings.
For example, suppose that we wanted to 
take a bunch of command line arguments and find out how many times
each argument occurs.
Overall, this means we want to collect the command line arguments,
then group them, and count them.

Let's build our way up to this because there is a lot we can learn from this.
\begin{lstlisting}
	x: "S"$ .z.x
\end{lstlisting}

Now can do something called ``grouping"

\begin{lstlisting}
g: group x
\end{lstlisting}

Grouping creates a ``dictionary" consisting (in this case)
of argument, position pairs.
For example, 
\begin{lstlisting}
q countargs.q dave was not here was not was
\end{lstlisting}

yields the following g:
\begin{lstlisting}
dave| ,0
was | 1 4 6
not | 2 5
here| ,3
\end{lstlisting}

Now type:

\begin{lstlisting}
key g
\end{lstlisting}

Then

\begin{lstlisting}
value g
\end{lstlisting}

Do you see what you are getting?

Now it is time to put the keys and the counts together.

\begin{lstlisting}
(key g),'(count each value g)
\end{lstlisting}

What is going on here?
$count$ just counts the number in a list.
The modifier (or ``adverb") each means that each list should
be counted separately.
The $,'$ means that we are taking each key and combining it with
the corresponding count.

\begin{framed}
Exercise 6: Find each argument with its $count$.
\end{framed}

\begin{framed}Exercise 7: Find the words tied for having the highest counts.\end{framed}

Here are some hints:

\begin{lstlisting}
y: (key g),'(count each value g)

y[;1]

x: 50 + 10 ? 6

max x

x[where x = max x]
\end{lstlisting}
\paragraph{Set Operations:}
Is every member of x also in y?

\begin{lstlisting}
subset:{[x;y] min x in y}
\end{lstlisting}

Find the elements of the x vector that are in a y vector
\begin{lstlisting}
intersect
\end{lstlisting}

Find those elements of x that are not in y
\begin{lstlisting}
difference
\end{lstlisting}
\vspace{30mm}
\lstinputlisting[language=q,firstline=0,lastline=11]{set.q}

\paragraph{String operations}
Delete all blanks in a line

\begin{framed}
Exercise: Write a multiintersect function

\begin{lstlisting}
/ deletes all blanks
delblanks:{[x] 
 ii: where not x = `` "; 
 x[ii] }
\end{lstlisting}
Take a string and separate it by blanks

\begin{lstlisting}
/ separate into words
sepwords:{[x]
  ii: where x = `` ";
  ii: distinct 0, ii;
  y: delblanks each ii _ x;
  c: count each y;
  ii: where not c = 0;
  y[ii]}
\end{lstlisting}
\end{framed}
$lower$ takes a string and puts it in lower case
$ltrim$ removes leading blanks; $rtrim$ trailing blanks

\begin{lstlisting}
``|" sv(``hey";``there") 		/yields ``hey|there"
` sv `foo`bar 					/yields `foo.bar
` sv `:/q`tutorial`draft1 		/yields	`:/q/tutorial/draft1 
2 sv 1000b 						/yields 8
`` " vs ``hey there" 			/yields (``hey"; ``there")
\end{lstlisting}
\begin{framed}
Exercise 8: Write a function that takes its command line arguments,
splits them based on underbars into k lists and finds the intersection
among those lists. All words should be reduced to lower case.

\begin{lstlisting}
q findinter A b c x _ D x a e b _ b b d X d
\end{lstlisting}

yields b x
\end{framed}
\paragraph{Other string ops}
\paragraph{Translation from k to q}: 
\begin{lstlisting}
ss[x;y] == ,/ x ,/:\: y
til 10  == !10
distinct x  == ? x
where x = 1 == & x = 1
first x == *x
min x == &/ x
max x == |/ x
reverse x == |x
x like y == x _sm y  / note that we can do things 
        like fl[ao]p / to mean either a or o
        like [09] / to mean 0 though 9
       like ``*[^09]" / strings that do not end with a digit
x ss y == x _ss y
enlist x == ,x
raze x  == ,/x
list1 cross list2 == ,/list1 ,/:\: list2

value group x == =x 
/group x == dictionary consisting of ?x and =x
\end{lstlisting}

Some things to note
1. In functions, must end lines with a semi-colon
yet it executes even without. But when it executes it
doesn't do the right thing. 
2. If I use find, I have to know the type of the entity I'm finding.
For example if I find among bits then I must say x ? 1b not x ? 1



\begin{thebibliography}{99}
\bibitem{shasha} Shasha, Dennis ``Q for smarties", 2011
\bibitem{kxref} Kx Systems, {\it https://code.kx.com/trac/wiki/Reference}, 2011
\end{thebibliography}
\end{document}
