Categories

Algorithm

Decouple the relation and approach in different metrics - kamelzcs's library

Decouple the relation and approach in different metrics

Posted on 2015-07-27 07:49:07 +0900 in Algorithm IPSC

Problem H – Humble Captains

The problem is given an undirected graph (Vertices<=300), and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices.

The key point lies in the way to count valid edges.

For each edge $e$ with two vertices $v1$, $v2$, define , then

Now try to find $count$ from vertices.

Then the final problem can be rephrased to look for a partition which minimizes the absolute difference between the sums of the numbers in each part, which could solved with dynamic programming easily.

This is really a nice problem, which requires to decouple the relations, and approach it in different metrics. The problem is found from Petr’s blog, official analysis.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SRM663 »

Hide Comments

comments powered by Disqus
posts

Latest

2015-07-27 Decouple the relation and approach in different metrics IPSC

C/C++

One C++ polymorphism quesion - kamelzcs's library

One C++ polymorphism quesion

Posted on 2015-05-24 19:58:27 +0900 in C/C++ C++ Polymorphism

Confusing subtype polymorphism

When I first began to learn the polymorphism of C++, the Subtype Polymorphism similar to the following confused me a lot.

//file cats.h
class Felid {
public:
 virtual void meow() = 0;
 void getName(){ std::cout << "This is the Felid\n\n"; }
};

class Cat : public Felid {
public:
 void meow() { std::cout << "Meowing like a regular cat! meow!\n"; }
 void getName(){ std::cout << "This is the Cat\n\n"; }
};

class Tiger : public Felid {
public:
 void meow() { std::cout << "Meowing like a tiger! MREOWWW!\n"; }
 void getName(){ std::cout << "This is the Tiger\n\n"; }
};

class Ocelot : public Felid {
public:
 void meow() { std::cout << "Meowing like an ocelot! mews!\n"; }
 void getName(){ std::cout << "This is the Ocelot\n\n"; }
};

Now the programme can uses different subtypes to call do_meowing.

#include <iostream>
#include "cats.h"

void do_meowing(Felid *cat) {
 cat->meow();
 cat->getName();
}

int main() {
 Cat cat;
 Tiger tiger;
 Ocelot ocelot;

 do_meowing(&cat);
 do_meowing(&tiger);
 do_meowing(&ocelot);
}

The output is:

Meowing like a regular cat! meow!
This is the Felid

Meowing like a tiger! MREOWWW!
This is the Felid

Meowing like an ocelot! mews!
This is the Felid

So, only the virtual function is polymorphism, but why and how?

polymorphisms in C++

There are four polymorphisms in C++, namely

  1. Subtype Polymorphism (Runtime Polymorphism)
  2. Parametric Polymorphism (Compile-Time Polymorphism)
  3. Ad-hoc Polymorphism (Overloading)
  4. Coercion Polymorphism (Casting)

virtual function belongs to the subtype polymorphism category.

subtype polymorphism implementation

Each object owns several fields, including

  1. data member
  2. inherited data member
  3. virtual table

subtype polymorphism in C++ is implemented by virtual table variable.

Also note that, member function is not stored in the object level, but in the class info level. So normal member function is only determined by its declared type, not polymorphismed.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-3-3 »

Hide Comments

comments powered by Disqus
posts

Latest

2015-05-24 One C++ polymorphism quesion C++ Polymorphism

Computer

Bash Command Line Processing - kamelzcs's library

Bash Command Line Processing

Posted on 2014-01-17 03:46:17 +0900 in Computer Bash

Command Line Processing

Each line the shell get is called a pipeline, it contains commands which are seperated by the pipe character(|). For each pipeline it gets, the shell will breaks it into commands, set up the I/O for the pipeline and follows the following figure to excecute the commands.

alt text

  1. Split the command into tokens by the metacharacters set: SPACE, TAB, NEWLINE, ;, (, ), <, >, |, and &. Types of tokens include: words, keywords, I/O redirectors, and semicolons.

  2. Checks the first token of each command to see if it is a keyword with no quotes or backslashes. If it is an opening keyword, such as if or orther control-structure openers, then the shell sets things up internally for compound commands, reads the next command, and start process again.

  3. Checks the first word of each command against the list of aliases. If a match is found, it substitudes and go back to Step 1. This scheme allows recursive aliases.

  4. Performs brace expansion. For example, a{b,c} becomes ab ac.

  5. Substitudes the user’s home directory($HOME) for tilde if it is at the beginning of a word.

  6. Performs parameter(variable) substitution for any expression that starts with a dollar sign($).

  7. Does command substitution for any expression of the form $(string).

  8. Evaluates arithmetic expressions of the form $((string)).

  9. Takes the parts of the line that resulted from parameter, command, and arithmetic substitution and splits them into words again. This time it uses the characters in $IFS which usually is whitespace (space, tab, and newline).

  10. Performs pathname expansion, a.k.a. wildcard expansion, for any occurrences of * ? and [/] pairs.

  11. Uses the first word as a command by looking up its source as a function command, then as a built-in, then as a file in any of the directories in $PATH

  12. Runs the command after setting up I/O redirection and other such things.

Reference

[1] Learning the bash shell

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 逝去的2013 »

Hide Comments

comments powered by Disqus
posts

Latest

2014-01-17 Bash Command Line Processing Bash

Contest

SRM663 - kamelzcs's library

SRM663

Posted on 2015-07-27 01:24:30 +0900 in Contest Topcoder

ChangingChange

Analyze

The constraint on D is the key to solve this problem.

As different ways are given, Generating function would be a great tool to hold all the info all at once.

Suppose ways = {1, 3, 6, 2}, then

By adding a coin whose value is 1, then new ways is

On the contrary, by removing a coin whose value is 1, the new ways is

By removing n coins, the new ways is

The coefficient of $x^k$ is which has to be developed.

$\implies$

The final answer would be

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Function_overriding in Java vs C++ »

Hide Comments

comments powered by Disqus
SRM 661 div1 - kamelzcs's library

SRM 661 div1

Posted on 2015-06-13 18:41:40 +0900 in Contest Topcoder

SRM 661 consists of 250 + 450 + 1000. 250 and 450 are two maths problems.

MissingLCM

Given $N \in [1,100000]$, find out the minimum $M \in (N, \infty)$ such that $lcm(1, 2, …, M)=lcm(N+1, N+2, …, M)$

Analyze

As $N$ is given, first consider how to calculate $lcm(1, 2, .., N)$

The answer would be only consider all the Prime number $P_i \in [1, N]$, and find out the maximum $n_i$ such that and then the answer would be

So should have all the factors. The the answer would be 

typedef long long LL;
class MissingLCM {
    public:
    bool isPrime[1000100];
    int getMin(int N) {
        if(N == 1){
            return 2;
        }
        for(int i = 1; i <= N; ++i){
            isPrime[i] = true;
        }
        for(int i = 2; i <= N; ++i){
            if(isPrime[i] == false){
                continue;
            }
            for(int j = 2 * i; j <= N; j += i){
                isPrime[j] = false;
            }
        }
        int ans = N;
        for(int i = 2; i <= N; ++i){
            if(isPrime[i] == false){
                continue;
            }
            int temp = i;
            while(temp <= N / i){
                temp *= i;
            }
            ans = max(ans, (N / temp + 1) * temp);
        }
        return ans;
    }
};

ColorfulLineGraphs

Analyze

suppose $f[N][K]$ is the total number of using $K$ colors on $N$ nodes.

Now considering to build $f[N][K]$ from $f[N-1][K]$

For node $N$ choose whether to link to some node $i \in [1,N-1]$ or do not link at all.

  1. linked to some node $i$, there are $K - 1$ ways of color possibilities each.
  2. do not link to any other, there are $K$ ways of color possibilities.

So

The current time complexity is $O(n)$, which is not fast enough.

Notice $M$ is small, would be cyclic, $M$ would be one periodic according to Lagrange’s theorem

typedef long long LL;
#define REP(i, N) for (int i = 0; i < (int)N; i++)

struct ColorfulLineGraphs {
  long long N;
  long long K;
  int M;
  int fastPower(LL base, LL p){
    int ans = 1;
    for(LL cur = 0; ((LL)1<<cur) <= p; ++cur){
      if(p & ((LL)1<<cur)){
        ans = (ans * base) % M;
      }
      base = (base * base) % M;
    }
    return ans;
  }
  int countWays(long long _N, long long _K, int _M) {
    N = _N, K = _K, M = _M;
    LL ans = 1, res = 1;
    K %= M;
    for(LL cur = 1; cur <= M; ++cur){
      res = (res * (cur * (K - 1) + 1)) % M;
      if(N % M == cur){
        ans = res;
      }
    }
    ans = (ans * fastPower(res, N / M)) % M;
    return ans;
  }
};
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | One C++ polymorphism quesion »

Hide Comments

comments powered by Disqus
posts

Latest

2015-07-27 SRM663 Topcoder
2015-06-13 SRM 661 div1 Topcoder

Data Science

From Jackknife to A/B Testing - kamelzcs's library

From Jackknife to A/B Testing

Posted on 2019-12-23 22:28:32 +0900 in Data Science Jackknife Math A/B Testing

Background

In A/B Testing, there is a group of data and , the metrics we interested in are the difference between these two groups and related confidence.

A Quick Introduction to Jackknife

Jackknife is a method of resample, which tries to estimate the bias and variability of an estimator by using values of on subsamples from .

The pseudovalue of is , where means the sample with value deleted from the sample.

Treat the pseudovalue as if they were independent random variables with mean , then the confidence interval could be obtained using Central Limit Theorem. Specifically, let

and

be the mean and sample variance of the pseudovalues. The jackknife 95% confidence interval is

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import math

sample_count = 500000
K = 5000
mu, sigma = 500, 100 # mean and standard deviation

def jackknife_sder(s):

    df = pd.DataFrame(data = s, columns=['data'])
    groups = int(sample_count / K )
    def label_race (row):
        return int(row.name) % groups
    df['group'] = df.apply(lambda row: label_race(row), axis=1)

    average = df['data'].mean()

    total_sum = s.sum()
    left_k_groups = [(total_sum - (df['data'][df['group'] == x]).sum()) / (sample_count - K) for x in range(groups)]
    a = groups * average
    b = [v * (groups - 1) for v in left_k_groups]
    ps = a - b 
    
    mean, var = ps.mean(), (ps.var(ddof = 1.0) / groups) ** 0.5
    return mean, var

data = [np.random.normal(mu, sigma, sample_count) for i in range(100)]
s_vars = [jackknife_sder(d) for d in data]
s_mean, s_var =  mu, sigma / (sample_count ** 0.5)

plt.hist(s_vars, bins=10)
plt.axvline(x=s_var, color='r', label=f'expected {s_var:.4f}')
plt.legend()
plt.show()

png

confidence = 1.96
l, r = (s_mean - confidence *  s_vars, s_mean + confidence *  s_vars)
print(f'left: {l:.4f}, right: {r:.4f}')



left: 499.7084, right: 500.2740
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
Monads »

Hide Comments

comments powered by Disqus
posts

Latest

2019-12-23 From Jackknife to A/B Testing Jackknife Math A/B Testing

Data structure

Linklist Mergesort - kamelzcs's library

Linklist Mergesort

Posted on 2014-01-24 03:27:36 +0900 in Data structure Datastructure Sourcecode

Linkedlist mergesort in Linux kernal

Merge sort on array can be easily done due to it is easy to find the specific data in a any given position index value. While, if it were the case in the linkedlist, it would be tough to implemente the mergesort efficienty.

Thanks to the post, I found the following source code in the Linux 2.6

/*
 * Returns a list organized in an intermediate format suited
 * to chaining of merge() calls: null-terminated, no reserved or
 * sentinel head node, "prev" links not maintained.
 */
static struct list_head *merge(void *priv,
				int (*cmp)(void *priv, struct list_head *a,
					struct list_head *b),
				struct list_head *a, struct list_head *b)
{
	struct list_head head, *tail = &head;

	while (a && b) {
		/* if equal, take 'a' -- important for sort stability */
		if ((*cmp)(priv, a, b) <= 0) {
			tail->next = a;
			a = a->next;
		} else {
			tail->next = b;
			b = b->next;
		}
		tail = tail->next;
	}
	tail->next = a?:b;
	return head.next;
}

The above code will merge two linked list. One extra struct *tail is being used to help construct the new linked list.

/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
 * This function implements "merge sort", which has O(nlog(n))
 * complexity.
 *
 * The comparison function @cmp must return a negative value if @a
 * should sort before @b, and a positive value if @a should sort after
 * @b. If @a and @b are equivalent, and their original relative
 * ordering is to be preserved, @cmp must return 0.
 */
void list_sort(void *priv, struct list_head *head,
		int (*cmp)(void *priv, struct list_head *a,
			struct list_head *b))
{
	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
						-- last slot is a sentinel */
	int lev;  /* index into part[] */
	int max_lev = 0;
	struct list_head *list;

	if (list_empty(head))
		return;

	memset(part, 0, sizeof(part));

	head->prev->next = NULL;
	list = head->next;

	while (list) {
		struct list_head *cur = list;
		list = list->next;
		cur->next = NULL;

		for (lev = 0; part[lev]; lev++) {
			cur = merge(priv, cmp, part[lev], cur);
			part[lev] = NULL;
		}
		if (lev > max_lev) {
			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
				printk_once(KERN_DEBUG "list passed to"
					" list_sort() too long for"
					" efficiency\n");
				lev--;
			}
			max_lev = lev;
		}
		part[lev] = cur;
	}

	for (lev = 0; lev < max_lev; lev++)
		if (part[lev])
			list = merge(priv, cmp, part[lev], list);

	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
}

The above code deals with the merge sort, which is really tricky and amazing. The key idea is in the

	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
						-- last slot is a sentinel */

This part will store the partial lists, whose lengths whill be where is the index of the part array.

It uses the Fibonacci property of the length in the mergesort list. Only the same length list of occur in the same specific position, and two same length lists will merge to a single list
whose length will double while the index in the part array is just the next postion.

At last, just merge all the elements in the part array, then the final list is constructed!

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Quoting and eval in Bash »

Hide Comments

comments powered by Disqus
posts

Latest

2014-01-24 Linklist Mergesort Datastructure Sourcecode

Functional Programming

Monads - kamelzcs's library

Monads

Posted on 2015-08-24 19:16:47 +0900 in Functional Programming Haskell CIS194

Lecture Contents

Type class really gives one good intuition about Monad.

Intuitively, it is this ability to use the output from previous computations to decide what computations to run next that makes Monad more powerful than Applicative. The structure of an Applicative computation is fixed, whereas the structure of a Monad computation can change based on intermediate results. This also means that parsers built using an Applicative interface can only parse context-free languages; in order to parse context-sensitive languages a Monad interface is needed

Category theory gives some theorems behind Monad.

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

Home Work

Exercise 2
battle :: Battlefield -> Rand StdGen Battlefield
battle b = do
    (aStream :: [DieValue]) <- getRandoms
    (bStream :: [DieValue]) <- getRandoms
    let rollPairs = zip (sort . take numAttackRolls   $ aStream)
                        (sort . take numDefenderRolls $ bStream)
    return $ foldl' (\newB (attackRoll, defendRoll) ->
                        if attackRoll > defendRoll
                        then newB { defenders = defenders newB - 1}
                        else newB { attackers = attackers newB - 1})
                    b
                    rollPairs
  where
    numAttackRolls   = min 3 (attackers b - 1)
    numDefenderRolls = min 2 (defenders b)
Exercise 3
invade :: Battlefield -> Rand StdGen Battlefield
invade bf@(Battlefield a b)
  | a == 1 || b == 0 = return bf
  | otherwise = battle bf >>= invade
Exercise 4
successProb :: Battlefield -> Rand StdGen Double
successProb bf = do
  let num = 10000
  results <- replicateM num (invade bf)
  return $ fromIntegral (wins results) / fromIntegral num
  where wins = length . filter ((==0) . defenders)

Test code:

*Risk> evalRandIO  $ successProb $ Battlefield 2 3
0.1338
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Applicative functors, Part II »

Hide Comments

comments powered by Disqus
Applicative functors, Part II - kamelzcs's library

Applicative functors, Part II

Posted on 2015-08-24 00:25:09 +0900 in Functional Programming Haskell CIS194

Lecture Contents

The classification about Levels of Abstraction is really great.

With respect to Applicative and Monad in particular, there are just two levels to be concerned with. The first is the level of implementing various Applicative and Monad instances, i.e. the “raw Haskell” level. Once we have an Applicative instance for a type like Parser, the point is that we get to “move up a layer” and program with Parsers using the Applicative interface, without thinking about the details of how Parser and its Applicative instance are actually implemented.

The powerful Type system of Haskell makes it really suitable to create Levels of Abstraction, which is usually very verbose or even impossible in other static typed programming languages.

Home Work

Exercise 1
zeroOrMore :: Parser a -> Parser [a]
zeroOrMore p = oneOrMore p <|> pure []

oneOrMore :: Parser a -> Parser [a]
oneOrMore p = (:) <$> p <*> zeroOrMore p
Exercise 2
spaces :: Parser String
spaces = zeroOrMore $ satisfy isSpace

ident :: Parser String
ident = (:) <$> (satisfy isAlpha) <*> zeroOrMore (satisfy isAlphaNum)
Exercise 3
-- An "identifier" is represented as just a String; however, only
-- those Strings consisting of a letter followed by any number of
-- letters and digits are valid identifiers.
type Ident = String

-- An "atom" is either an integer value or an identifier.
data Atom = N Integer | I Ident
  deriving Show

-- An S-expression is either an atom, or a list of S-expressions.
data SExpr = A Atom
           | Comb [SExpr]
  deriving Show

parseAtom :: Parser Atom
parseAtom = spaces *> (N <$> posInt <|> I <$> ident) <* spaces

parseComb :: Parser SExpr
parseComb = spaces *> (Comb <$> (char '(' *> oneOrMore parseSExpr <* char ')')) <* spaces

parseSExpr :: Parser SExpr
parseSExpr = (A <$> parseAtom) <|> parseComb

Test:

*SExpr> runParser parseSExpr "(   lots  of   (  spaces   in  )  this ( one ) )"
Just (Comb [A (I "lots"),A (I "of"),Comb [A (I "spaces"),A (I "in")],A (I "this"),Comb [A (I "one")]],"")
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Applicative functors, Part I »

Hide Comments

comments powered by Disqus
Applicative functors, Part I - kamelzcs's library

Applicative functors, Part I

Posted on 2015-08-23 19:40:32 +0900 in Functional Programming Haskell CIS194

Lecture Contents

The induction from Functor to Applicative is quite beautiful.

Recalled that there exists fmap :: (a -> b) -> (f a -> f b) in Functor, it would be great if this mapping function is still valid if the input consists of more than one variable, namely (a -> b -> c) -> (f a -> f b -> f c)

We have

h  :: a -> b -> c
fa :: f a
fb :: f b
fc :: f c

Use fmap to lift functions,

h         :: a -> (b -> c)
fmap h    :: f a -> f (b -> c)
fmap h fa :: f (b -> c)

But there is no way to make

f (b -> c) -> fb -> fc

Applicative has the (<*>) to implement it, namely

(<*>) :: f (a -> b) -> f a -> f b

The final induction is

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 = h <$> fa <*> fb

Home Work

Exercise 1
-- Ex. 1 - implement a Functor instance for Parser
--
-- You may find it useful to implement:
-- first :: (a -> b) -> (a,c) -> (b,c)

first :: (a -> b) -> (a, c) -> (b, c)
first f (x, y) = (f x, y)

instance Functor Parser where
  fmap f parser = Parser $ \s -> first f <$> runParser parser s
Exercise 2
-- Ex. 2 - implement an Applicative instance for Parser
--
instance Applicative Parser where
  pure a = Parser (\s -> Just (a, s))

  p1 <*> p2 = Parser parse
    where parse s = do
          r1 <- runParser p1 s
          r2 <- runParser p2 (snd r1)
          return (fst r1 $ fst r2, snd r2)
Exercise 3
-- Ex. 3a - Create a parser:
--
--   abParser :: Parser (Char, Char)
--
-- which expects to see the characters ’a’ and ’b’ and returns them as a pair

abParser :: Parser (Char, Char)
abParser = (,) <$> char 'a' <*> char 'b'


-- Ex. 3b - Create a parser:
--
--   abParser_ :: Parser ()
--
-- which acts in the same way as abParser but returns () instead of 'a' and 'b'

abParser_ :: Parser ()
abParser_ = const . const () <$> char 'a' <*> char 'b'

-- Ex. 3c - Create a parser:
--
--   intPair 
--
-- which reads two integer values separated by a space and returns the integer 
-- values in a list. You should use the provided posInt to parse the integer values.

intPair :: Parser [Integer]
intPair = (\x  y -> [x, y]) <$> posInt <* char ' ' <*> posInt
Exercise 4
instance Alternative Parser where
  empty = Parser $ const Nothing
  Parser p1 <|> Parser p2 = Parser $ liftA2 (<|>) p1 p2
Exercise 5
-- Ex. 5 - Implement a parser:
--
--  intOrUppercase :: Parser ()
-- 
-- which parses either an integer value or an uppercase character, and fails otherwise.

intOrUppercase :: Parser ()
intOrUppercase = const () <$> posInt <|> const () <$> satisfy isUpper
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | IO »

Hide Comments

comments powered by Disqus
IO - kamelzcs's library

IO

Posted on 2015-08-22 06:08:38 +0900 in Functional Programming Haskell CIS194

Lecture Contents

There is no String “inside” an IO String, IO String is a promise, to produce a String requires actually executing the computation. And the only way to do that is to give it (perhaps as part of some larger IO value) to the Haskell runtime system, via main.

Home Work

Exercise 1
-- 1. define glCons, which adds an Employee to GuestList

glCons :: Employee -> GuestList -> GuestList
glCons e (GL es fun) = GL (e:es) (fun + empFun e)


-- 2. define a Monoid instance for GuestList

instance Monoid GuestList where
  mempty  = GL [] 0
  mappend (GL es1 f1) (GL es2 f2) = GL (es1 ++ es2) $ f1 + f2

-- 3. define moreFun, which takes two GuestLists and returns the one
-- which has more fun

moreFun :: GuestList -> GuestList -> GuestList
moreFun = max
Exercise 2
treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f (Node a []) = f a []
treeFold f (Node a forest) = f a (map (treeFold f) forest)
Exercise 3
nextLevel :: Employee -> [(GuestList, GuestList)] -> (GuestList, GuestList)
nextLevel b gls = (withBoss, withoutBoss)
  where
    withoutBoss = mconcat $ map (uncurry moreFun) gls
    withBoss = glCons b $ mconcat $ map snd gls
Exercise 4
maxFun :: Tree Employee -> GuestList
maxFun = uncurry moreFun . treeFold nextLevel
Exercise 5
formatGLS :: GuestList -> String
formatGLS (GL es fun) =
  totalStr ++ "\n" ++ nameStr
  where
    totalStr = "Total fun: " ++ show fun
    nameStr = unlines $ sort $ map empName es

main :: IO ()
main = readFile "company.txt" >>= putStrLn . formatGLS . maxFun . read
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Folds and monoids »

Hide Comments

comments powered by Disqus
Folds and monoids - kamelzcs's library

Folds and monoids

Posted on 2015-08-21 01:32:54 +0900 in Functional Programming Haskell CIS194

Lecture Contents

To understand the different relations between type classes, Type class is a great reference.

This is a fantastic picture.

Home Work

Exercise 1
(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
l1 +++ l2 = Append (tag l1 `mappend` tag l2) l1 l2
Exercise 2
-- 1. Implement the function indexJ to find the JoinList element at
-- the specified index; it should satisfy the equivalence:
--     (indexJ i jl) == (jlToList jl !!? i)

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ i _ | i < 0 = Nothing
indexJ i (Single _ _) | i > 0 = Nothing
indexJ _ (Single _ a) = Just a
indexJ i p@(Append _ l r)
  | i >= sz p = Nothing
  | i < lsize = indexJ i l
  | otherwise = indexJ (i - lsize) r
  where lsize = sz l

-- 2. Implement the function dropJ to drop first n elements of a
-- JoinList; it should satisfy the equivalence:
--     jlToList (dropJ n jl) = drop n (jlToList jl)

dropJ :: (Sized b, Monoid b) => Int -> JoinList b a ->JoinList b a
dropJ _ Empty        = Empty
dropJ n l | n < 0 = l
dropJ _ (Single _ _) = Empty
dropJ n (Append _ l r)
  | n < lsize = (dropJ n l) +++ r
  | otherwise = dropJ (n - lsize) r
  where lsize = sz l

-- 3. Implement the function takeJ to return the first n elements of a
-- JoinList, dropping all other elements; it should satisfy the equivalence:
--     jlToList (takeJ n jl) == take n (jlToList jl)

takeJ :: (Sized b, Monoid b) => Int -> JoinList b a ->JoinList b a
takeJ _ Empty          = Empty
takeJ n _  | n < 0    = Empty
takeJ n j | n + 1 >= sz j = j
takeJ n (Append _ l r)
  | n < lsize = takeJ n l
  | otherwise = l +++ takeJ (n - lsize) r
  where lsize = sz l
Exercise 3
module Scrabble where

import Data.Monoid

data Score = Score Int
             deriving (Eq, Show)

instance Monoid Score where
  mempty = Score 0
  Score a `mappend` Score b = Score (a+b)

score :: Char -> Score
score c
  | c `elem` "aeilnorstuAEILNORSTU" = Score 1
  | c `elem` "dgDG"                 = Score 2
  | c `elem` "bcmpBCMP"             = Score 3
  | c `elem` "fhvwyFHVWY"           = Score 4
  | c `elem` "kK"                   = Score 5
  | c `elem` "jxJX"                 = Score 8
  | c `elem` "qzQZ"                 = Score 10
  | otherwise                       = Score 0

scoreString :: String -> Score
scoreString = foldr ((<>).score) $ Score 0

Test code:

*JoinList> scoreLine "yay " +++ scoreLine "haskell!"
Append (Score 23) (Single (Score 9) "yay ") (Single (Score 14) "haskell!")
Exercise 4

The magical part is (Sized b, Monoid b) restriction to Sized (a,b).

To make it valid, besides the auto implemented

instance (Monoid a, Monoid b) => Monoid (a,b) where
mempty = (mempty, mempty)
mappend (a1,b1) (a2,b2) = (mappend a1 a2, mappend b1 b2)

The functions in Sized.hs is also critical.

instance Sized Size where
  size = id

-- This instance means that things like
--   (Foo, Size)
--   (Foo, (Bar, Size))
--   ...
-- are all instances of Sized.
instance Sized b => Sized (a,b) where
  size = size . snd

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

Thanks to these functions, the previously implemented indexJ, dropJ, takeJ are still valid to the (Score, Size)

type JLBuffer = JoinList (Score, Size) String

instance Buffer JLBuffer where

  -- toString :: JLBuffer -> String
  toString = concat . jlToList

  -- fromString :: String -> JLBuffer
  fromString = foldr1 (+++) . map(\x -> Single (scoreString x, Size 1) x) . lines

  -- line :: Int -> JLBuffer -> Maybe String
  line = indexJ

  -- replaceLine :: Int -> String -> JLBuffer -> JLBuffer
  replaceLine n str jlb =
    takeJ (n - 1) jlb +++ Single (scoreString str, Size 1) str +++ dropJ n jlb

  -- numLines :: JLBuffer -> Int
  numLines = sz

  -- value :: JLBuffer -> Int
  value = scorev . fst . tag
          where scorev (Score i) = i

-- JLBuffer based editor

main :: IO()
main = runEditor editor jlb
  where jlb = fromString $ unlines
         [ "This buffer is for notes you don't want to save, and for"
         , "evaluation of steam valve coefficients."
         , "To load a different file, type the character L followed"
         , "by the name of the file."
         ] :: JLBuffer
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Lazy evaluation »

Hide Comments

comments powered by Disqus
Lazy evaluation - kamelzcs's library

Lazy evaluation

Posted on 2015-08-18 20:18:10 +0900 in Functional Programming Haskell CIS194

Lecture Contents

Lazy evaluation is beautiful because it makes infinite data structures possible. But it makes reasoning about the programme harder, especially when mixed with side effects.

import Data.Array

knapsack01 :: [Double]   -- values 
           -> [Integer]  -- nonnegative weights
           -> Integer    -- knapsack size
           -> Double     -- max possible value
knapsack01 vs ws maxW = m!(numItems-1, maxW)
  where numItems = length vs
        m = array ((-1,0), (numItems-1, maxW)) $
              [((-1,w), 0) | w <- [0 .. maxW]] ++
              [((i,0), 0) | i <- [0 .. numItems-1]] ++
              [((i,w), best) 
                  | i <- [0 .. numItems-1]
                  , w <- [1 .. maxW]
                  , let best
                          | ws!!i > w  = m!(i-1, w)
                          | otherwise = max (m!(i-1, w)) 
                                            (m!(i-1, w - ws!!i) + vs!!i)
              ]

example = knapsack01 [3,4,5,8,10] [2,3,4,5,9] 20

The functional dynamic programming implementation is kind of tricky in my view.

Monolithic Arrays is used to memorized the overlapped subprobramme.

Home Work

Exercise 1
fib :: Integer -> Integer
fib n
  | n == 0 = 0
  | n == 1 = 1
  | otherwise = fib (n - 1) + fib (n - 2)

fibs1 :: [Integer]
fibs1 = map fib [0..]
Exercise 2
fibs2 :: [Integer]
fibs2 = 0 : 1 : zipWith (+) fibs2 (tail fibs2)
Exercise 3

cons is mentioned in the lecture, but use record syntax makes it much more cleaner.

data Stream a = Stream { streamToList :: [a] }

instance (Show a) => Show (Stream a) where
  show =  show . take 20 . streamToList
Exercise 4
streamRepeat :: a -> Stream a
streamRepeat = Stream . repeat

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f = Stream . map f . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f = Stream . iterate f
Exercise 5

Explanation

nats :: Stream Integer
nats = Stream [0..]

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Stream (x:xs)) s =
  Stream $ x : streamToList (interleaveStreams s (Stream xs))


ruler :: Stream Integer
ruler = foldr1 interleaveStreams (map streamRepeat [0..])
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | More polymorphism and type classes »

Hide Comments

comments powered by Disqus
More polymorphism and type classes - kamelzcs's library

More polymorphism and type classes

Posted on 2015-08-18 01:01:33 +0900 in Functional Programming Haskell CIS194

Lecture Contents

f :: a -> a -> a
f x y = x && y

The reason this doesn’t work is that the caller of a polymorphic function gets to choose the type. Here we, the implementors, have tried to choose a specific type

a -> a -> a

could be understood as a promise that a function with this type will work no matter what type the caller chooses

Type classes

Intuitively, type classes correspond to sets of types which have certain operations defined for them, and type class polymorphic functions work only for types which are instances of the type class(es) in question

Home Work

Exercise 1
eval :: ExprT -> Integer
eval (Lit i) = i
eval (Add e1 e2) = eval e1 + eval e2
eval (Mul e1 e2) = eval e1 * eval e2
Exercise 2
evalStr :: String -> Maybe Integer
evalStr = fmap eval . parseExp Lit Add Mul
Exercise 3

Defination for Expr

module Expr where

class Expr a where
  lit :: Integer -> a
  add :: a -> a -> a
  mul :: a -> a -> a
instance Expr ExprT where
  lit = Lit
  add = Add
  mul = Mul

reify :: ExprT -> ExprT
reify = id
Exercise 4
instance Expr Integer where
  lit = id
  add = (+)
  mul = (*)

instance Expr Bool where
  lit i
    | i <= 0 = False
    | i > 0  = True
  add = (||)
  mul = (&&)

newtype MinMax = MinMax Integer
                 deriving (Eq, Show)

instance Expr MinMax where
  lit = MinMax
  add (MinMax x) (MinMax y) = MinMax (max x y)
  mul (MinMax x) (MinMax y) = MinMax (min x y)

newtype Mod7 = Mod7 Integer
                 deriving (Eq, Show)

instance Expr Mod7 where
  lit x = Mod7 (x `mod` 7)
  add (Mod7 x) (Mod7 y) = Mod7 ((x+y) `mod` 7)
  mul (Mod7 x) (Mod7 y) = Mod7 ((x*y) `mod` 7)
Exercise 5
instance Expr Program where
  lit x = [PushI x]
  add x y = x ++ y ++ [Add]
  mul x y = x ++ y ++ [Mul]
Exercise 6

There are two tricky parts from my view:

  1. Same expression can belong to multiple types, both add (lit 3) (var "x") :: (M.Map String Integer -> Maybe Integer) and add (lit 3) (var "x") :: VarExprT are valid

  2. add e1 e2 m has the type of (M.Map String Integer -> Maybe Integer) -> (M.Map String Integer -> Maybe Integer) -> (M.Map String Integer -> Maybe Integer)

data VarExprT = Lit Integer
              | Add VarExprT VarExprT
              | Mul VarExprT VarExprT
              | Var String
                deriving (Eq, Show)

instance Expr VarExprT where
  lit = Lit
  add = Add
  mul = Mul

class HasVars a where
  var :: String -> a

instance HasVars VarExprT where
  var = Var

instance HasVars (M.Map String Integer -> Maybe Integer) where
  var = M.lookup

instance Expr (M.Map String Integer -> Maybe Integer) where
    lit =  const . Just
    add e1 e2 m = (+) <$> e1 m <*> e2 m
    mul e1 e2 m = (*) <$> e1 m <*> e2 m

withVars :: [(String, Integer)]
         -> (M.Map String Integer -> Maybe Integer)
         -> Maybe Integer
withVars vs exp = exp $ M.fromList vs
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Higher-order programming and type inference »

Hide Comments

comments powered by Disqus
Higher-order programming and type inference - kamelzcs's library

Higher-order programming and type inference

Posted on 2015-08-17 19:46:29 +0900 in Functional Programming Haskell CIS194

Lecture Contents

There is an art to deciding the order of arguments to a function to make partial applications of it as useful as possible: the arguments should be ordered from from “least to greatest variation”, that is, arguments which will often be the same should be listed first, and arguments which will often be different should come last.

The only reason why this ordering makes sense is the last one could be made point free when it is in need.

One thing confuses me a lot is the difference between $ and . when doing the function composition.

stackoverflow gives a great answer. To summarize,

  • $ operator is for avoiding parenthesis.Anything appearing after it will take precedence over anything that comes before.
  • . operator is for chaining functions. It works like the pipeline, the output on the right goes to the input of the left.
putStrLn (show (1 + 1)) == putStrLn $ show $ 1 + 1 == putStrLn . show $ 1 + 1

Exercise

Exercise 1 Wholemeal programming
fun1 :: [Integer] -> Integer
fun1 = foldr (\x y -> if even x then (x - 2) * y else y) 1

fun2:: Integer -> Integer
fun2 = sum . filter even . takeWhile (> 1) . iterate (\n -> if even n then n `div` 2 else 3 * n + 1)
Exercise 2 Folding with trees

Always try to insert into the left subtree while keep it is balanced.

data Tree a = Leaf | Node Integer (Tree a) a (Tree a)
            deriving Show

foldTree :: [a] -> Tree a
foldTree xs = foldr insert Leaf xs
    where
        height Leaf = -1
        height (Node h _ _ _) = h
        count Leaf = 0
        count (Node _ l _ r) = 1 + count l + count r
        insert x Leaf = Node 0 Leaf x Leaf
        insert x (Node h l d r)
            | height l > height r = Node h l d $ insert x r
            | count l > count r   = Node h l d (insert x r)
            | otherwise           = let newl = insert x l
                                        newHeight = (1 + (height newl))
                                        in Node newHeight newl d r
Exercise 3 More folds
xor :: [Bool] -> Bool
xor = foldr (\x accum -> if x then not accum else accum) False

map' :: (a -> b) -> [a] -> [b]
map' f = foldr (\x accum -> f x : accum) []
Exercise 4 Finding primes
sSundDelete :: Int -> [Int]
sSundDelete n = [i+j+2*i*j|i<-[1..n], j<-[i..n]]

sieveSundaram :: Int -> [Int]
sieveSundaram n = let del = sSundDelete n in
     [2*x+1 | x <- [1..n], not (x `elem` del)]
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Recursion patterns, polymorphism, and the Prelude »

Hide Comments

comments powered by Disqus
Recursion patterns, polymorphism, and the Prelude - kamelzcs's library

Recursion patterns, polymorphism, and the Prelude

Posted on 2015-08-17 01:13:17 +0900 in Functional Programming Haskell CIS194

Lecture Content

In fact, experienced Haskell programmers hardly ever write recursive functions!

This is quite unbelieable for me at first glance. Even though recursive function is not the best practice in languages which does not provide tail call optimization.

Recursive function provide more abstract way than iterative function, while there exists more abstract way than Recursive function, which leave the low-level details of actually doing recursion to these functions.

Infix Function

Backticks can turn any standard function with two argumetns in an infix operator which is called section syntax:

(op e)  =   \ x -> x op e
(e op)  =   \ x -> e op x

For example,

elem 2 [1, 2, 3] == (2 `elem`) [1, 2, 3] == ((`elem` [1, 2, 3]) 2)

Exercise 1 Hopscotch

zip or zipwith are convenient to do filter in list.

skips :: [a] -> [[a]]
skips xs =
        let ns = [1..length xs]
            extractEvery m = map snd . filter (\x -> (fst x `mod` m) == 0) . zip ns
            in map (`extractEvery` xs) ns

Exercise 2 Local maxima

localMaxima :: [Integer] -> [Integer]
localMaxima (a:b:c:xs)
    | b > a && b > c = b: p
    | otherwise = p
    where
        p = localMaxima(b:c:xs)
localMaxima _ = []

Exercise 3 Histogram

histogram:: [Integer] -> String
histogram xs =
        let count = map (\n -> length $ filter (== n) xs) [0..9]
            maxi = maximum count
            histo m (base, c) = show base ++ "=" ++
                replicate c '*' ++
                replicate (m - c) ' '
        in
           unlines . reverse . transpose . map (histo maxi) $ zip [0..9] count

Test code,

*Golf> putStr $ histogram [1,1,1,5]
 *        
 *        
 *   *    
==========
0123456789
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Algebraic Data Types »

Hide Comments

comments powered by Disqus
Algebraic Data Types - kamelzcs's library

Algebraic Data Types

Posted on 2015-08-16 23:42:59 +0900 in Functional Programming Haskell CIS194

Lecture Content

Algebraic data types in general
data AlgDataType = Constr1 Type11 Type12
                 | Constr2 Type21
                 | Constr3 Type31 Type32 Type33
                 | Constr4

This is the general Algebraic data types definition.

One important note:

  • type and data constructor names must always start with a capital letter
  • variables(including names of functions) must always start with a lowercase letter

Home Work

Exercise 1
parseMessage :: String -> LogMessage
parseMessage s = case words s of
  ("I":t:xs) -> LogMessage Info (read t) (unwords xs)
  ("W":t:xs) -> LogMessage Warning (read t) (unwords xs)
  ("E":c:t:xs) -> LogMessage (Error $ read c) (read t) (unwords xs)
  _ -> Unknown s

parse :: String -> [LogMessage]
parse = map parseMessage . lines
Exercise 2
insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) m = m
insert m Leaf = Node Leaf m Leaf
insert m (Node l lg r)
  | mT < logT = Node (insert m l) lg r
  | otherwise = Node l lg (insert m r)
  where
    getTimeStamp x = case x of (LogMessage _ t _)-> t
                               _ -> 0
    mT = getTimeStamp m
    logT = getTimeStamp lg
Exercise 3
build :: [LogMessage] -> MessageTree
build = foldr insert Leaf
Exercise 4
inOrder :: MessageTree -> [LogMessage]
inOrder Leaf = []
inOrder (Node l lg r) = inOrder l ++ [lg] ++ inOrder r
Exercise 5
whatWentWrong :: [LogMessage] -> [String]
whatWentWrong = map getMsg . filter seri . inOrder . build
  where seri (LogMessage (Error e) _ _) = e >= 50
        seri _ = False
        getMsg (LogMessage _ _ m) = m

Test code:

*LogAnalysis> testWhatWentWrong parse whatWentWrong "sample.log" 
["Way too many pickles","Bad pickle-flange interaction detected","Flange failed!"]
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Introduction to Haskell »

Hide Comments

comments powered by Disqus
Introduction to Haskell - kamelzcs's library

Introduction to Haskell

Posted on 2015-08-15 22:16:12 +0900 in Functional Programming Haskell CIS194

Lecture Content

Among all of them, Pure is the most tricky part. In the current computer system model, side effects are inevitable. Haskell uses Modad and treats the outside world as static to implement Pure.

Home Work

Exercise 1
toDigits :: Integer -> [Integer]
toDigits n
  | n <= 0 = []
  | otherwise = toDigits (n `div` 10) ++ [n `mod` 10]

toDigitsRev :: Integer -> [Integer]
toDigitsRev = reverse . toDigits

Test part,

ex1Tests :: [Test]
ex1Tests = [ testF1 "toDigits test" toDigits
             [(1234, [1, 2, 3, 4]), (5, [5]), (0, []), (-17, [])]
           ]
Exercise 2

The key lies in generating infinite lists of [1, 2, 1, 2, ...] There are several ways to generate infinite lists.

numbers1 = 1 : map (+1) numbers1
numbers2 = 1 : [x+1 | x <- numbers2]
numbers3 = [1..]

The way to get infinite interchange of 1 2 lists is

  oneTwo = 1 : 2 : oneTwo
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = reverse . zipWith (*) oneTwo . reverse where
  oneTwo = 1 : 2 : oneTwo

Test code

ex2Tests :: [Test]
ex2Tests = [testF1 "doubleEveryOther test" doubleEveryOther
             [([8, 7, 6, 5], [16, 7, 12, 5]), ([1, 2, 3], [1, 4, 3])]
           ]
Exercise 3
sumDigits :: [Integer] -> Integer
sumDigits = sum . map (sum. toDigits)
ex3Tests :: [Test]
ex3Tests = [testF1 "sumDigits test" sumDigits
             [([16, 7, 12, 5], 22)]
           ]
Exercise 4
validate :: Integer -> Bool
validate = (== 0) . (`mod` 10) . sumDigits . doubleEveryOther . toDigits
ex4Tests :: [Test]
ex4Tests = [testF1 "validate test" validate
             [(4012888888881881, True), (4012888888881882, False)]
           ]
Exercise 5
type Peg = String
type Move = (Peg, Peg)

hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c
  | n <= 0 = []
  | n == 1 = [(a, b)]
  | otherwise = hanoi (n - 1) a c b ++ [(a, b)] ++ hanoi (n - 1) c b a
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Learn Haskell »

Hide Comments

comments powered by Disqus
Learn Haskell - kamelzcs's library

Learn Haskell

Posted on 2015-08-14 02:11:25 +0900 in Functional Programming Haskell

Why Functional Programming

In the current world, tons of programming languages exist now, and tons of new ones are being created.

Imperative Programming

I am more confident in C, Python, only familliar with C++ and Java in some sense.

  • C is consise and small, but lacks a lot of libraries in its standard. It is used to implement critical componenet such as Kernel, PostgreSQL, Redis, etc. It worths when the system efficiency overweights the developing speed.

  • C++ is powerful but much too complex. The compiler does a lot of things behind the scene. It really costs to learn the specific conditions in the compiler, such as function overloading, Numeric promotions, Rule of three, etc.

  • Java is much simpler than C++, which is highly portable on JVM and truly object oriented. It consists of tons of frameworks and libraries, but is really verbose. It is used to build large softwares and is still popuar in big companies which provide web services.

  • Python is really simple glue language. Due to its simplicity, people around the world not only the professional programmers are contributing all kinds of libraries. As it is dynamic typing, it is hard to build large system.

In my view, the key of Imperative Programming lies in controlling side effects which make the programme hard to reason about and buggy.

How Functional Programming shines

In Python, function is the first class, and it supports some basic FP features such as map, reduce, list comprehention, etc. I find it really cool to have the following features,

Why Haskell

How to learn Haskell

As exercise plays an important role in learning, I would like to follow the suggestions in learn haskell, first finish CIS194, then try NICITA.

Here is the source code for CIS194.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Decouple the relation and approach in different metrics »

Hide Comments

comments powered by Disqus
posts

Latest

2015-08-24 Monads Haskell CIS194
2015-08-24 Applicative functors, Part II Haskell CIS194
2015-08-23 Applicative functors, Part I Haskell CIS194
2015-08-22 IO Haskell CIS194
2015-08-21 Folds and monoids Haskell CIS194

Life

说好的2014 - kamelzcs's library

说好的2014

Posted on 2015-02-09 19:27:53 +0900 in Life Review

工作

2014年，职业生涯真正开始的一年，在所谓的Full-Stack 上迈出了第一步。

前端

前端上加入了一个照片上传的插件，没错，这个货就是Javascript。 看着它那略怪异的各种语法， 然后小心的查着各种Tips，读着Good parts, 查着Bad parts，生怕跌入深坑。 开源大法好，要是让我开发这个玩意，没有个几年时间肯定做不出既能兼容各种浏览器，又具有很好的扩展性，同时 又经过严格的单元测试的项目。

Jascript就是这样，在给予一个最简单的跨平台的展示媒介的情况下，却不得不“忍受”它与生俱来的各种问题。

除此之外，开始使用Jinja2来生成Html，也要调试一些CSS相关的代码。

前端的东西还是Trick太多，无论是语言的设计还是各种浏览器的兼容。

App Engine

在App Engine的项目上加入了一个绿坝系统，在App Engine扩展性限制下，用了最简单的关键词+正则表达的方式。大部分的精力花在了用Jinja2处理 复杂的前端Html页面上面。前端和后端一样，甚至比后端更需要抽象。因为前端需求变动的情况更多，同时展现涉及的页面 也更多，抽象不好，然后每一次页面的修改都会变为O(N)的人肉暴力。

基于语义的过滤系统肯定最准确，但是计算量太大。退而求其次，在分词的基础上进行匹配处理，效果就会好的多。 基于Lucene的Elastic Search应该是做这个最方便的工具。

尝试做了到NoSQL的Migration。后来想想，在目标Web服务器及数据库都没有确定的情况下，这个工作实在难以评价效果。 最大的收获还是线下开发，然后推入EC2测试，最后评价的整个流程走了一遍。Google的工具还是太高端了，因为系统拆分成了 多个模块，然后拥有非常优秀的可扩展性及灵活性。这是只使用工具所不能拥有的成就感。

自动化配置-Ansible

完成了一个自动化配置工具-Ansible的项目。系统自动化配置Web服务器Tornado，数据库Postgresql，任务队列Celery与Nginx，RabbitMQ, Supervisor, Iptable, Redis。同时可以在配置文件中修改各种参数，不用再为系统环境的兼容性上苦恼。

Ansbile的优点为用Python实现，上手容易。但是因为它依赖Yaml与Jinja2等已有工具，所以在DSL解释的过程中，有不少陷阱。Python还是太不 适合用来实现DSL了。如果目标为长期的大型复杂项目，应该考虑其他的工具，如基于Ruby的Puppet等。

异步ORM

做了一个Tornado与Postgresql之间的异步ORM。在个人看来，这是今年做的最有价值的工作。不知为何，现在没有开源的基于SQL的异步ORM。 虽然现在的这个ORM非常简陋，但是支持CURD及可支持嵌套的Transaction。 基本思路和工具都是在不断阅读相关项目的代码及文档，不断的思考，同时在网络上请教，最终一点点攒起来的。 思路很简单，Peewee的DSL部分+Momoko的线程Pool及执行部分+Peewee的resultwrapper部分。

Peewee是一个简单强大的ORM, 但是对Raw SQL的支持有限，究其原因还是resultwrapper很简单，并不是对SQL语句进行解释分析的。

第一次在实际工程中用到Compiler里面学到的东西。虽然只是一个用Python解释的DSL前端。Python的DSL是用重载运算符实现的，这一点直观上容易混淆。 别的方面，学到了Mixin在动态加载时改变代码执行路径，Python的胶水特性。

学习

阅读的源代码：

  • Tornado: 代码的文档及注释都很出色，代码质量也可靠。
  • Peewee: 短小精悍，只用了三千行就写出了一个这么出色的ORM。
  • Momoko: Raw SQL runner + Thread Pool

阅读的书籍：

  • Lisp 系列
    • The Little Schemer: 简单易懂，最后推倒出了Y表达式。
    • The Seasoned Schemer: 关注更简洁、抽象的函数表达式。
    • The Reasoned Schemer: Logic Programming， 脑洞大开。
  • SICP: 读过两遍，试题略略的看了一下。不得不说这是一本神书，每一个对编译语音有兴趣的人，都会从中学到很多。
  • Haskell Books: 对Haskell产生兴趣先是由于各种传说，后来读了之后发现，要掌握好这门语言，居然要学习Category Theory, 瞬间好感度上升一个数量级。
    • Learn you a Haskell for Great Good
    • The Real World Haskell
  • Introduction to Algorithm: 重读了部分常用算法，简洁、从直觉出发，算法设计的经典书籍。
  • Compiler course in Stanford: 主要精力花在了前端的整个算法理解上，优化及IR，二进制码实现略看了下。比龙书易懂，适合入门。
  • The Economist: 自从日元贬值开始，开始发现金融界的事情开始和自己有莫大的关系。现在停留在看热闹的阶段，主要关注中国及亚洲版。
  • 日语系列: 多掌握一门语言，据说就多了一种选择。英语确实有极大的用处，日语现在的最大的用处还是处在简单的吹牛，读读杂志的阶段。
    • 初级日本语上、下
    • 中级日本语上、下
    • 大家的日语初级

可量化的成绩

  • 日语N2
  • 编程相关
    • 被fork的项目Vim
    • 被Star的项目Google Analytics
    • Patch被Accepted项目
      • Momoko
      • Ansbile playbook

总结

2014年学习了Web开发的各种语言，各种工具，可以独立的承担一些项目。 2014年并未如原来曾有的乐观一样，出现突飞猛进的变化。根本原因，大的目标不明确。 涉猎了不少东西，但是真正能量化的成绩却非常少。 这也与设立目标时总是关注目标本身，却缺少量化的可考量的手段。 就像是在跑步时，没有明确要跑多少，而是告诉自己，尽量跑。 没有可量化的目标，很难超出自己的心理舒适期，更无法超越自己的极限。 无法超越极限，水平自然停滞不前。 自己曾经尝试过独立的优化或者在一些工具上开发一些项目。但是最终都以失败而告终。 总结其中的原因，目标与现实的能力水平有差异。在没有真正兴趣的情况下选择一个新的领域 或者是在仅仅知道皮毛，却想独立一步作成一个大的项目的野望。

脚踏实地，立足现在，寻求合伙人，设立可量化的目标，总结与纠正，不断向前。 确立大的目标，然后分解成小的可量化目标，定期评价总结。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Goals in 2014 »

Hide Comments

comments powered by Disqus
逝去的2013 - kamelzcs's library

逝去的2013

Posted on 2014-01-06 07:41:07 +0900 in Life Life Review

实习生活

过完新年之后的第一个周一，北上帝都。炮君先我一步，与高富帅看好了房子。到了帝都的第一天，在中介的 半忽悠之后，签下了第一份房租合同。略带新鲜，但是失落感很强的帝都生活开始了。

第一家实习的公司算是较大的公司，各方面较为正规，但是所做的事情是自己原来涉及较少的，从头学起是不得不经历的过程。 摸索着用起来了Linux，写起了Python，开始与Excel打交道，阅读关于公司技术框架与业务的文档。看着这个只有十几年历史 的互联网公司的框架，偶尔还能看到读大一大二时就已经耳闻的前辈们留下的文档与代码。在这里，我是1/20000。我是一颗 螺丝钉，想从人堆里面出头，是很难的事情。

但是大公司最大的好处就是培训的课程多，可以在上班的时候学习公司的training课程。线下帝都有特别多的技术交流的活动， 如果不介意帝都那阴沉的天空和让人望而生畏的房价，这里，应该是国内长技术的好地方。

50天的实习，在技术上没有明显的进步，倒是公司的文档与课程让我大开眼界。原来仅有耳闻的技术早已经在使用了。只是，这里 只是我的一个过渡的站点。

走川西

第一次也是唯一的一次外出露营,难以忘记在野外的快乐，或许我本身就是一个放荡不羁的人，在野外，我可以放肆的笑，可以傻傻的 看着花花草草发呆，可以在4600米海拔的地方裸露自己的上身，与神圣的贡嘎山合影。

一次又一次的被美丽的川西折服，一次又一次的赞叹自然的造化与人类精神上的纯洁与伟大。当我们出现高原反应的时候，是寺庙的方丈 无偿的给我们红景天泡水。当我第一次那么近距离的仰望满天的繁星的时候，我的心中除了满满的赞叹与心中的崇敬，毫无他念。

川西，一定要好好的走一遍，不至少一遍。川西，请等我。

毕业

七年之痒，毕业了。这三年是失去的三年，当初的意气风发被消耗了很多。当初已经能改变世界，后来，我没有能够改变世界， 只能尽量不要让世界改变了我。本科毕业的时候，我忙的不可开交，有很多的朋友要分别，有很多的事情要处理。这最后的毕业， 我居然是如此的清闲，没有未来的扑面而来的压迫，也没有自己迫不及待的期望，真正要分别的朋友也少了很多。

是我把自己封闭了，故作清高的认为周围值得自己认识的人很少，同时在找不到更好的目标的情况下，当我消极失落的时候，更多的 时间留给了三国杀和足球。

我是一个多么肤浅的人，即使技术上这不是一个领先的地方，我有网线，网络上，难道自己想努力，还不能找到适合自己的圈子？ 我是一个多么肤浅的人，即使身边看到的优秀的同学不够多，但是，本科的学弟学妹们，在非技术方面优秀的同学难道不足以给自己 更多可以学习的启示？自己的知识系统是如此的不完善，难道有其他专长的同学不值得自己学习？封闭了自己，就是一个信息的孤岛， 信息的孤岛怎么能够与时俱进呢？

如果线下不能有一群志同道合的朋友的话，利用好每一个社交的工具，尽力的追赶，然后尽快的创造自己的圈子。总有很多人值得自己 学习，在每一个方面！

驾照你好

从7.5号考完理论，到9.4号拿到驾照，不足俩月。期间的考试都是一次性通过，比较满足。学手艺与学技术在我看来没有特别大的区别， 天赋与努力依然是互相依存的。

当然也见到了不少社会中略肮脏的交易，不想向它妥协，除了自己变强，没有它法。改变环境，没有相应的能力与影响，谈何容易。 即使有了相应的能力与影响，这也谈何容易。

日语

接触日语应该有一年了，认真学习也有三四个月了。略有进步，但是同日本人交流依然问题很大，语法现在慢慢的懂了不少，但是单词 是最大的问题。除了每周周日去小学学习日语以外，每天说日语的时候少的可怜。说更多的日语，才能更好的掌握日语。更多的讲日语， 从与Cathy对话开始。

工作

开始了公司的工作，在一个没有文档的框架上开发，同时又是基于App Engine的，这是有多的sucks，眼泪直流。不过，同事还好，老板 还好，push的不多，不懂的方法与技术慢慢的摸索与学习。只是每天都至少加班一个小时，让人略伤感。公司的人都是自动加班，暂时还 不知道这是为什么，或许这是日企的文化吧，慢慢体验。珍爱生命，原理加班，提高效率！

更专业，更细致

加入了一只足球队，这是我第一次尝试加入日本人的圈子。很开心，很受打击，也很受教育。大家对我都很客气，队长对我也非常的照顾。 日本人专业的精神，让我赞叹。每次练习赛，都会有主裁、边裁，甚至都有入场仪式。而且每次训练前提前两周左右安排已经做好。他们是 如此的专业，这样做上10年，还会有什么不清楚的呢？对长辈的尊敬，不仅仅是出于礼节上，更主要的是别人比自己更专业！

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Understanding Git »

Hide Comments

comments powered by Disqus
posts

Latest

2015-02-09 说好的2014 Review
2014-01-06 逝去的2013 Life Review

Linux

Quoting and eval in Bash - kamelzcs's library

Quoting and eval in Bash

Posted on 2014-01-20 19:15:24 +0900 in Linux Bash

Quoting and eval in Bash

Quoting

Quoting in Bash actually skips some steps in the previous post:

  1. Sinle quotes('') bypass through the Step 10. Everything inside the Single quotes remains untouched. There can’t be single quotes inside single quotes, even if bashslashes are used.

  2. Double quotes("") bypass Step 1 through 4, plus steps 9 and 10. Single quotes inside double quotes has no effect. But doulbe quotes allow for parameter substitution, command substitution and arithmetic expression evaluation. A double quote can be inside another double quote by a backslash.

Eval

Eval lets the precess being precessed once more. It tells the shell to take the eval’s arguments and run them through the command-line precessing steps all over again.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Bash Command Line Processing »

Hide Comments

comments powered by Disqus
posts

Latest

2014-01-20 Quoting and eval in Bash Bash

Programming

Function_overriding in Java vs C++ - kamelzcs's library

Function_overriding in Java vs C++

Posted on 2015-06-22 17:27:24 +0900 in Programming Java C++

Similar code, different behaviour

Quesion in stackoverflow:

Java version:

class base{
    public void func1(){
        func2();
    }
    public void func2(){
        System.out.println(" I am in base:func2() \n");
    }

}

class derived extends base{
    public void func1(){
        super.func1();
    }
    public void func2(){
        System.out.println(" I am in derived:func2() \n");
    }
};
public class Test
{
    public static void main(String[] args){
        derived d = new derived();
        d.func1();
    }
}

Output:

I am in derived:func2()

C++ version

#include <stdio.h>

class base
{
    public:
        void func1(){
            func2();
        }
        void func2(){
            printf(" I am in base:func2() \n");
        }
};

class derived : public base
{
    public:
        void func1(){
            base::func1();
        }
        void func2(){
            printf(" I am in derived:func2() \n");
        }
};

int main()
{
    derived *d = new derived();
    d->func1();
    return 0;
}

Output:

I am in base:func2()

Why

Firstly, I thought the behaviour of C++ is reasonable, Java version is hard to understand, as I am more used to static binding.

For both languages, variable binding is static, no matter it is member variable or not.

But for method binding, two languages behaviour differently.

In C++, unless this method is virtual, otherwise it is bind staticlly default.

but in Java, all method bindings use late binding unless it is static or final(private is implicly final).

Java version behaves as if you had declared base::func2 as

virtual void func2(){
    printf(" I am in base:func2() \n");
}

Static Binding vs Late Binding

static binding means references are resovled at compile time, namely it is possible to resolve it by its position.

late binding means references are resolved at run time, which is implemented through Vtable in C++.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SRM 661 div1 »

Hide Comments

comments powered by Disqus
posts

Latest

2015-06-22 Function_overriding in Java vs C++ Java C++

SICP

sicp-4-3-3 - kamelzcs's library

sicp-4-3-3

Posted on 2015-03-16 21:02:58 +0900 in SICP Lisp

4.51

It would always be (a b 1).

4.52

(define (analyze-if-fail exp)
   (let ((first (analyze (cadr exp)))
         (second (analyze (caddr exp))))
     (lambda (env succeed fail)
       (first env
              (lambda (value fail2)
                (succeed value fail2))
              (lambda ()
                (second env succeed fail))))))

4.53

(let ((pairs '()))
  (if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110))))
             (permanent-set! pairs (cons p pairs))
             (amb))
           pairs))

pairs would collect all the combinations of the two lists. (amb) would force iterate all the valid pairs which would be returned.

4.54

(define (analyze-require exp)
  (let ((pproc (analyze (require-predicate exp))))
    (lambda (env succeed fail)
      (pproc env
             (lambda (pred-value fail2)
               (if (not (true? pre-value))
                   (fail2)
                   (succeed 'ok fail2)))
             fail))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-3-2 »

Hide Comments

comments powered by Disqus
sicp-4-3-2 - kamelzcs's library

sicp-4-3-2

Posted on 2015-03-15 06:36:17 +0900 in SICP Lisp

4.39

    (require (> miller cooper))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require
     (distinct? (list baker cooper fletcher miller smith)))(require (not (= (abs (- fletcher cooper)) 1)))

The answer will always be correct, but the efficiency would be different.

By putting the more restrictive in the front makes the branch cutting happens earlier.

4.40

(define (multiple-dwelling)
 (let ((cooper (amb 2 3 4 5))
       (miller (amb 3 4 5)))
   (require (> miller cooper))
   (let ((fletcher (amb 2 3 4)))
     (require (not (= (abs (- fletcher cooper)) 1)))
     (let ((smith (amb 1 2 3 4 5)))
       (require (not (= (abs (- smith fletcher)) 1)))
       (let ((baker (amb 1 2 3 4)))
         (require
           (distinct? (list baker cooper fletcher miller smith)))
         (list (list 'baker baker)
               (list 'cooper cooper)
               (list 'fletcher fletcher)
               (list 'miller miller)
               (list 'smith smith)))))))

4.41

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

(define (filter predicate sequence)
  (cond ((null? sequence) '())
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (permutations lst)
  (if (null? lst)
    (list '())
    (flatmap
      (lambda (first)
        (map
          (lambda (rest) (cons first rest))
          (permutations (filter (lambda (x) (not (= x first))) lst))))
      lst)))

(permutations '(1 2 3 4 5))

permutations function is the key point.

4.42

(define (xor a b)
  (or (and a (not b))
      (and (not a)b)))

(define liars
  (let ((betty (amb 1 2 3 4 5))
        (ethel (amb 1 2 3 4 5))
        (joan (amb 1 2 3 4 5))
        (kitty (amb 1 2 3 4 5))
        (mary (amb 1 2 3 4 5)))
    (require
      (distinct? (list betty ethel joan kitty mary)))
    (require (xor (= kitty 2) (= betty 3)))
    (require (xor (= ethel 1) (= joan 2)))
    (require (xor (= joan 3) (= ethel 5)))
    (require (xor (= kitty 2) (= mary 4)))
    (require (xor (= mary 4) (= betty 1)))
    (list (list 'betty betty)
          (list 'ethel ethel)
          (list 'joan joan)
          (list 'kitty kitty)
          (list 'mary mary))))

One important thing to note is, and and or is not a regular primitive function in Scheme, classification is here, it must be dealt with separatly.

4.44

(define (safe? result)
  (let ((p (car result)))
    (define (conflict? q i)
      (or
        (= p q)
        (= p (+ q i))
        (= p (- q i))))
    (define (check rest i)
      (cond
        ((null? rest) true)
        ((conflict? (car rest) i) false)
        (else (check (cdr rest) (+ i 1)))))
    (check (cdr result) 1)))

(define (queens n)
  (define (iter result left)
    (if (= 0 left)
      result
      (begin
        (let ((new (cons (an-integer-between 1 n)
                         result)))
          (require (safe? new))
          (iter new (- left 1))))))
  (iter '() n))

(queens 8)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-3-1 »

Hide Comments

comments powered by Disqus
sicp-4-3-1 - kamelzcs's library

sicp-4-3-1

Posted on 2015-03-13 22:47:34 +0900 in SICP Lisp

I just find 4.3 very hard to understand. Eventhough I followed the author’s ideas, and find it work.

But this time I found even try to understand the callings through debug would be very difficult.

There should be theoretical foundations for this, finally, though this tutorial, I found the idea befind it is CPS. There are other materials here, here.

4.35

(define (an-integer-between low high)
  (require (<= low high))
  (amb low (an-integer-between (+ low 1) high)))

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

(a-pythagorean-triple-between 1 100)

4.36

(define (a-pythagorean-triple-from low)
  (let ((k (an-integer-starting-from low)))
    (let ((i (an-integer-between low k)))
      (let ((j (an-integer-between i k)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

(a-pythagorean-triple-from 1)

4.37

It would cut many useless branches.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-2-3 »

Hide Comments

comments powered by Disqus
sicp-4-2-3 - kamelzcs's library

sicp-4-2-3

Posted on 2015-03-12 20:27:03 +0900 in SICP Lisp

4.32

In the current version, car is lazy as well, which makes it possible to build structures such as infinite tree.

4.33

;'(a b c)-->(cons 'a (cons 'b (cons 'c '())))

((quoted? exp) (text-of-quotation exp env))

(define (list->cons lst)
  (if (null? lst)
    '()
    (list 'cons
          (list 'quote (car lst))
          (list->cons (cdr lst)))))

(define (text-of-quotation exp env)
  (let ((quoted-operand (cadr exp)))
    (if (pair? quoted-operand)
      (eval (list->cons quoted-operand) env)
      quoted-operand)))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-2-1 »

Hide Comments

comments powered by Disqus
sicp-4-2-1 - kamelzcs's library

sicp-4-2-1

Posted on 2015-03-11 19:20:01 +0900 in SICP Lisp

4.25

(define (unless condition usual-value exceptional-value)
  (if condition exceptional-value usual-value))

(define (factorial n)
  (unless (= n 1)
    (* n (factorial (- n 1)))
    1))

In applicative-order, factorial will enter an infinite loop, as the exceptional-value is evaluated regardless the condition.

While in normal-order, the condition is judged before exceptional-value is evaluated.

4.26

(define (unless? exp) (tagged-list? exp 'unless))
(define (unless-clauses exp) (cdr exp))
(define (unless-condition clauses) (car clauses))
(define (unless-usual-value clauses) (cadr clauses))
(define (unless-exceptional-value clauses) (caddr clauses))
(define (unless->if exp)
  (expand-unless-clauses (unless-clauses exp)))
(define (expand-unless-clauses clauses)
  (make-if (unless-condition clauses)
           (unless-exceptional-value clauses)
           (unless-usual-value clauses)))

It would fail if unless is passed as parameter, as there is no such procedure.

4.27

(define count 0)
(define (id x)
  (set! count (+ count 1))
  x)

(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
1
;;; L-Eval input:
w
;;; L-Eval value:
10
;;; L-Eval input:
count
;;; L-Eval value:
2

(define w (id (id 10))) will cause the outer id being force, (id 10) is not evaluated and being returned as a thunk.

The evaluation of w forces the inner id being forced.

4.28

I think it would cause trouble if the operator is a thunk instead of actual procedure. In order to make the operator be a thunk, the easiest way is to pass the procedure as a parameter. such as:

(define (g x) (+ x 1))
(define (f g x) (g x))
(f g 10)

4.29

;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
100
;;; L-Eval input:
count
;;; L-Eval value:
1 ; with memorization, (id 10) is called once.
2 ; without memorization, (id 10) is called twice

To test the efficiency, simillar to the 4.24 problem.

(eval '(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n))) the-global-environment)

(let ((t0 0) (t1 0))
  (define (loop i n)
    (eval '(factorial 1234) the-global-environment)
    (if (< i n)
      (loop (+ i 1) n)))
  (set! t0 (runtime))
  (loop 0 1)
  (set! t1 (runtime))
  (- t1 t0))

;9.864471 second without memorization
;0.027408 second with memorization

4.30

  1. display is a primitive function, so Ben is right.
  2. with original version, (p1 1) = (1,2) and (p2 1) = 1 while in Cy’s version, both of them would be (1, 2).
(define (p2 x)
  (define (p e)
    e
    x)
  (p (set! x (cons x '(2)))))

(set! x (cons x '(2))) is passed in as a thunk parameter e of the internal p procedure in the original version and is not forced as it is not passed to a primitive procedure.

  1. Obviously.
  2. I prefer the text’s. As lazy evalution is better not involved with side effects.
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-1-6-4-1-7 »

Hide Comments

comments powered by Disqus
sicp-4-1-6-4-1-7 - kamelzcs's library

sicp-4-1-6-4-1-7

Posted on 2015-03-09 23:37:54 +0900 in SICP Lisp

4.16

a:

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (if (equal? (car vals) '*unassigned*)
               (error "Unassigned variable" var)
               (car vals)))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
      (error "Unbound variable" var)
      (let ((frame (first-frame env)))
        (scan (frame-variables frame)
              (frame-values frame)))))
  (env-loop env))

b:

(define (scan-out-defines body)
  (let* ((definitions (filter definition? body))
         (rest-of-lambda (filter (lambda (x)
                                   (not (definition? x)))
                                 body))
         (symbols (map cadr definitions))
         (let-body (map (lambda (s) (list s ''*unassigned*))
                              symbols))
         (set-body (map (lambda (s) (list 'set! (cadr s) (caddr s)))
                        definitions)))
    (if (null? let-body)
      body
      (list (append (list 'let let-body) set-body rest-of-lambda)))))

This part is tricky, which took me several hours to make it.

  1. ''*unassigned* needs two single quotes. Because '*unassigned* is the value of a variable.
  2. The returned value should be in a list.
  3. The (null? let-body) should be used, otherwise it would loop forever.

4.17

There is an extra frame in the transformed program because let is transformed to a lambda call.

To make the scope role “simultaneous” without creating a new frame, the internal definations could be extract to the top before being runned.

(define (rearrange body)
  (let* ((definitions (filter definition? body))
         (rest-of-lambda (filter (lambda (x)
                                   (not (definition? x)))
                                 body)))
    (append definitions rest-of-lambda)))

4.18

Both this version and the original version would not work, as the values of u and v are evaluated directly without through other proxy values.

4.19

The footnote gives the opinion of the author. It is complicated implement the simutaneous, even though Topological sort could be used to deal with simple defination order problem.

But when the mutual_recursion happens, it would not be possible to get the actual defination order at all. For racket:

(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))

a: undefined;
 cannot use before initialization

4.20

(define (letrec? exp) (tagged-list? exp 'letrec))
(define (letrec->let exp)
  (let* ((assi (let-associations exp))
         (rest-of-lambda (let-body exp))
         (symbols (map car assi))
         (let-body (map (lambda (s) (list s ''*unassigned*))
                              symbols))
         (set-body (map (lambda (s) (list 'set! (car s) (cadr s)))
                        assi)))
    (if (null? let-body)
      exp
      (append (list 'let let-body) set-body rest-of-lambda))))

letrecis evaluated includes all the letrec bindings, while let is not.

4.21

((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
        1
        (* k (ft ft (- k 1)))))))
 10)

;-->
((lambda (ft k)
   (if (= k 1)
     1
     (* k (ft ft (- k 1)))))
 (lambda (ft k)
   (if (= k 1)
     1
     (* k (ft ft (- k 1)))))
 10)

;-->
(if (= 10 1)
  1
  (* 10
     ((lambda (ft k)
        (if (= k 1)
          1
          (* k (ft ft (- k 1)))))
      (lambda (ft k)
        (if (= k 1)
          1
          (* k (ft ft (- k 1)))))
      9)))

;-->
(* 10
   ((lambda (ft k)
      (if (= k 1)
        1
        (* k (ft ft (- k 1)))))
    (lambda (ft k)
      (if (= k 1)
        1
        (* k (ft ft (- k 1)))))
    9)))
(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) true (od? ev? od? (- n 1))))
   (lambda (ev? od? n)
     (if (= n 0) false (ev? ev? od? (- n 1))))))

$\lambda$ makes functional programming possible.

4.22

((let? exp) (analyze (let->combination exp)))

Analyze is able to handle it.

4.23

execute-sequence has cond and other extra commands, while the text version is just some runnable procedure.

(lambda (env)
  ((lambda (env) 
     (proc1 env) 
     (proc2 env))
   env)
  (proc3 env))

4.24

(eval '(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n))) the-global-environment)

(let ((t0 0) (t1 0))
  (define (loop i n)
    (eval '(factorial 1234) the-global-environment)
    (if (< i n)
      (loop (+ i 1) n)))
  (set! t0 (runtime))
  (loop 0 200)
  (set! t1 (runtime))
  (- t1 t0))

For original version: $3.302853$ second, while for optimized version $2.106789$ second.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-1-3-4-1-5 »

Hide Comments

comments powered by Disqus
sicp-4-1-3-4-1-5 - kamelzcs's library

sicp-4-1-3-4-1-5

Posted on 2015-03-06 20:12:10 +0900 in SICP Lisp

4.11

(define (make-frame variables values)
  (if (= (length variables) (length values))
    (map cons variables values)
    (error "length mismatch -- MAKE-FRAME" variables values)))

(define (frame-variables frame) (map car frame))
(define (frame-values frame) (map cdr frame))

4.12

I can only come up with a find-binding-frame function and manually controls its process under different situations. But Zhang come up with a more higher level abstraction which only expose two functions to all the rest logic, which is null-action and eq-action. Clean and robust!

(define (env-loop var null-action eq-action env)
  (define (scan vars vals)
    (cond ((null? vars)
           (null-action env))
          ((eq? var (car vars))
           (eq-action vals))
          (else (scan (cdr vars) (cdr vals)))))
  (if (eq? env the-empty-environment)
    (error "Unbound variable" var)
    (let ((frame (first-frame env)))
      (scan (frame-variables frame)
            (frame-values frame)))))

(define (set-variable-value! var val env)
  (define (null-action e)
    (env-loop var null-action eq-action (enclosing-environment e)))
  (define (eq-action vs)
    (set-car! vs val))
  (env-loop var null-action eq-action env))

(define (lookup-variable-value var env)
  (define (null-action e)
    (env-loop var null-action eq-action (enclosing-environment e)))
  (define eq-action car)
  (env-loop var null-action eq-action env))

(define (define-variable! var val env)
  (define (null-action e)
    (add-binding-to-frame! var val (first-frame e)))
  (define (eq-action vs)
    (set-car! vs val))
  (env-loop var null-action eq-action env))

4.13

 (define (make-unbound variable env)
   (let ((vars (frame-variables (first-frame env)))
         (vals (frame-values (first-frame env))))
     (define (unbound vars vals new-vars new-vals)
       (cond ((null? vars)
              (error "variable is not in the environment -- MAKE-UNBOUND"
                     variable))
             ((eq? (car vars) variable)
              (set-car! env
                        (cons (append new-vars (cdr vars))
                              (append new-vals (cdr vals)))))
             (else (unbound (cdr vars) (cdr vals)
                            (append  new-vars (list (car vars)))
                            (append  new-vals (list (car vals)))
     (unbound vars vals '() '())))

4.14

((application? exp)
 (apply (eval (operator exp) env)
        (list-of-values (operands exp) env)))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ...)

(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))

When eval '(map + '(1 2) '(3 4)), primitive procedure + is evaluated as '(primitive +). Then expression becomes (apply-in-underlying-scheme map '(primitive +) '(1 2) '(3 4)), then failed.

4.15

(define (run-forever) (run-forever))
(define (try p)
  (if (halts? p p)
    (run-forever)
    'halted))

There are two possible outcomes to run (try try), either returns halted or runs forever.

  1. (try try) returns halted: then it would fall into the (run-forever) trap. Contradiction.
  2. (try try) runs forever: then the first condition is false, halted is returned. Contradiction.
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-4-1 »

Hide Comments

comments powered by Disqus
sicp-4-1 - kamelzcs's library

sicp-4-1

Posted on 2015-03-06 00:51:11 +0900 in SICP Lisp

4.1

It takes me several minutes to really understand the quanstion. :(

It really only has something to do with the order of the parameter evaluation. To restrict the order, the parameters passed in to cons should be taken out explicitly before being used.

(define (list-of-values-left-right exps env)
  (if (no-operands exps)
    '()
    (let ((left (eval (first-operand exps) env)))
      (cons left
            (list-of-values-left-right (rest-operands exps) env)))))

4.2

A procedure application is any compound expression that is not one of the above expression types. The car of the expression is the operator, and the cdr is the list of operands

The problem lies in the way to determain a procedure which is much too simple.

If it is put at the very beginning, then (define x 3) would be recognized as a procedure, the operator of which is define and the operands are x and 3. But at that time, there is no procedure called define at all.

(define (application? exp) (tagged-list? exp 'call))
(define (operator exp) (cadr exp))
(define (operands exp) (cddr exp))

4.4

((and? exp) (eval-and exp env))
((or? exp) (eval-or exp env))
(define (and? exp)
  (tagged-list? exp 'and))
(define (eval-and exp env)
  (define (eval-and-operands operands)
    (cond ((null? operands) false)
          ((true? (eval (car operands) env))
           (eval-and-operands (cdr operands)))
          (else false)))
  (eval-and-operands (cdr exp)))

(define (or? exp)
  (tagged-list? exp 'or))
(define (eval-or exp env)
  (define (eval-or-operands operands)
    (cond ((null? operands) false)
          ((true? (eval (car operands) env))
           true)
          (else
           (eval-or-operands (cdr operands)))))
  (eval-or-operands (cdr exp)))

;derived version
((and? exp) (eval (and->if exp) env))
((or? exp) (eval (or->if exp) env))

(define (and? exp)
  (tagged-list? exp 'and))
(define (and-clauses exp) (cdr exp))
(define (expand-and-clauses clauses)
  (if (null? clauses)
      'true
      (make-if (car clauses)
               (expand-and-clauses (cdr clauses))
               'false)))
(define (and->if exp)
  (expand-and-clauses (and-clauses exp)))

(define (or? exp)
  (tagged-list? exp 'or))
(define (or-clauses exp) (cdr exp))
(define (expand-or-clauses clauses)
  (if (null? clauses)
      'false
      (make-if (car clauses)
               'true
               (expand-or-clauses (cdr clauses)))))

(define (or->if exp)
  (expand-or-clauses (or-clauses exp)))

The tricky thing is the type of the return value. For derived expression, the returned type is some data, while for other kinds, it would return some code.

4.5

(define (expand-clauses clauses)
  (if (null? clauses)
    'false                          ; no else clause
    (let ((first (car clauses))
          (rest (cdr clauses)))
      (if (cond-else-clause? first)
        (if (null? rest)
          (sequence->exp (cond-actions first))
          (error "ELSE clause isn't last -- COND->IF" clauses))
        (let ((test (cond-predicate first))
              (recepient (if (eq? (car (cond-actions first)) '=>)
                           (cadr (cond-actions first))
                           false)))
          (make-if test
                  (if recepient
                    (list recepient test) ;test-recepient cond
                    (sequence->exp (cond-actions first))) ;normal cond
                  (expand-clauses rest)))))))

4.6

 (define (let? expr) (tagged-list? expr 'let))
 (define let-associations cadr)
 (define (let-vars expr) (map car (let-associations expr)))
 (define (let-value expr) (map cadr (let-associations expr)))
 (define (let-body expr) (cddr expr))
 (define (let->combination expr)
   (cons (make-lambda (let-vars expr) (let-body expr))
         (let-value expr)))

4.7

 (define (let*? expr) (tagged-list? expr 'let*))
 (define (let*-body expr) (caddr expr))
 (define (let*-inits expr) (cadr expr))
 (define (let*->nested-lets expr)
   (let ((inits (let*-inits expr))
         (body (let*-body expr)))
     (define (make-lets exprs)
       (if (null? exprs)
         body
         (list 'let (list (car exprs)) (make-lets (cdr exprs)))))
     (make-lets inits)))

4.8

It should be transformed like this.

(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))
 (define (named-let->func expr) 
     (list 'define  
           (cons (named-let-func-name expr) (named-let-func-parameters expr)) 
           (named-let-func-body expr))) 
  
 (define (let->combination expr) 
     (if (named-let? expr) 
         (sequence->exp 
           (list (named-let->func expr) 
                 (cons (named-let-func-name expr) (named-let-func-inits expr)))) 
         (cons (make-lambda (let-vars expr) 
               (list (let-body expr))) 
               (let-inits expr))))

4.9

(define (while->combination expr)
  (sequence->exp
    (list (list 'define
                (list 'while-iter)
                (make-if (while-condition expr)
                         (sequence->exp (list (while-body expr)
                                              (list 'while-iter)))
                         'true))
          (list 'while-iter))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-5-4-3-5-5 »

Hide Comments

comments powered by Disqus
sicp-3-5-4-3-5-5 - kamelzcs's library

sicp-3-5-4-3-5-5

Posted on 2015-03-05 06:11:43 +0900 in SICP Lisp

3.77

 (define (integral delayed-integrand initial-value dt)
   (cons-stream
     initial-value
     (let ((integrand (force delayed-integrand)))
       (if (stream-null? integrand)
         the-empty-stream
         (integral
           (delay (stream-cdr integrand))
           (+ (* dt (stream-car integrand)) initial-value)
           dt)))))

3.78

 (define (integral delayed-integrand initial-value dt)
   (cons-stream
     initial-value
     (let ((integrand (force delayed-integrand)))
       (if (stream-null? integrand)
         the-empty-stream
         (integral
           (delay (stream-cdr integrand))
           (+ (* dt (stream-car integrand)) initial-value)
           dt)))))
(define (solve-2nd a b dt y0 dy0)
  (define y (integral (delay dy) y0 dt))
  (define dy (integral (delay ddy) dy0 dt))
  (define ddy
    (add-streams
      (scale-stream dy a)
      (scale-stream y b)))
  y)

3.79

 (define (general-solve-2nd f y0 dy0 dt)
   (define y (integral (delay dy) y0 dt))
   (define dy (integral (delay ddy) dy0 dt))
   (define ddy (stream-map f dy y))
   y)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-5-3 »

Hide Comments

comments powered by Disqus
sicp-3-5-3 - kamelzcs's library

sicp-3-5-3

Posted on 2015-03-03 22:24:29 +0900 in SICP Lisp

3.63

guess is used to share the computation result between the succssive calling. Otherwise each call to sqrt-stream x would require recursively calling.

If memo-proc is not used, these two versions would be the same efficiency.

3.64

(define (stream-limit s tolerance)
  (let ((s2 (stream-cdr s)))
    (if (< (abs
             (-
               (stream-car s)
               (stream-car s2)))
           tolerance)
      (stream-car s2)
      (stream-limit s2 tolerance))))

3.65

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))
(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))
(define (log2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (log2-summands (+ n 1)))))
(define log2-stream
  (partial-sums (log2-summands 1)))

(stream-limit
  (accelerated-sequence euler-transform log2-stream) 0.0001)

3.66

1 2 4 6 8
  3 5 9 13
    7 11 19
      15 23

The order to traverse the pair is listed as above. Some observations:

$(i,i)=2^i-1$

$(i, i + 1) = 3*2^{i-1}-1$

$(i, k) = 3*2^{i-1}-1 + (k- i - 1) * 2^i$

3.67

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
     (interleave
       (stream-map (lambda (x) (list (stream-car s) x))
                   (stream-cdr t))
       (stream-map (lambda (x) (list x (stream-car t)))
                   (stream-cdr s)))
     (pairs (stream-cdr s) (stream-cdr t)))))

3.68

Only the cons-stream is a normal-order function, while interleave is not. When interleave evaluate its two parameters, which includes pair, would lead to infinite loop.

3.69

(define (triples s1 s2 s3)
  (cons-stream
    (list (stream-car s1)
          (stream-car s2)
          (stream-car s3))
    (interleave
      (stream-map
        (lambda (x) (append (list (stream-car s1))
                            x))
        (stream-cdr
          (pair s2 s3)))
      (triples (stream-cdr s1)
               (stream-cdr s2)
               (stream-cdr s3)))))

3.70

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
          (let ((s1car (stream-car s1))
                (s2car (stream-car s2)))
            (if (<= (weight s1car)
                    (weight s2car))
              (cons-stream s1car
                           (merge-weighted (stream-cdr s1)
                                           s2
                                           weight))
              (cons-stream s2car
                           (merge-weighted s1
                                           (stream-cdr s2)
                                           weight)))))))

(define (weighted-pairs s t weight)
  (cons-stream
    (list (stream-car s) (stream-car t))
    (merge-weighted
      (stream-map
        (lambda (x) (list (stream-car s) x))
        (stream-cdr t))
      (weighted-pairs
        (stream-cdr s)
        (stream-cdr t)
        weight)
      weight)))

(weighted-pairs integers
                integers
                (lambda (x)
                  (apply + x)))

(define no-factors
  (stream-filter
    (lambda (x)
      (not
        (or (divides? x 2)
            (divides? x 3)
            (divides? x 5))))
    integers))

(weighted-pairs no-factors
                no-factors
                (lambda (lst)
                  (let ((i (car lst))
                        (j (cadr lst)))
                    (+
                      (* 2 i)
                      (* 3 j)
                      (* 5 i j)))))

3.71

(define (sum-cube pair)
  (let ((i (car pair))
        (j (cadr pair)))
    (+ (* i i i)
       (* j j j))))

(define all-pairs
  (weighted-pairs integers integers sum-cube))

(define (ram-numbers stream)
  (let* ((w1 (sum-cube
               (stream-car stream)))
         (rest (stream-cdr stream))
         (w2 (sum-cube
               (stream-car rest))))
    (if (= w1 w2)
      (cons-stream w1
                   (ram-numbers (stream-cdr
                                  rest)))
      (ram-numbers rest))))

(show-stream (ram-numbers all-pairs) 6)

3.73

(define (RC r c dt)
  (lambda (i v)
    (add-streams
      (scale-stream i r)
      (integral (scale-stream i
                              (/ 1 c))
                v
                dt))))

3.74

(define zero-crossings
  (stream-map sign-change-detector sense-data
              (cons-stream 0 sense-data)))

3.75

The last value of the origin stream should be passed in, otherwise avpt would acutally become a recursive version.

3.76

(define (smooth s)
  (stream-map (lambda (x y) (/ (+ x y) 2))
              (cons-stream 0 s)
              s))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-5-1-3-5-2 »

Hide Comments

comments powered by Disqus
sicp-3-5-1-3-5-2 - kamelzcs's library

sicp-3-5-1-3-5-2

Posted on 2015-03-02 20:24:25 +0900 in SICP Lisp

Code from the text.

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))
(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(stream-ref
   (stream-enumerate-interval 1 100)
   10)

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

3.50

(define (stream-map proc . argstreams)
  (if (null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

(define s1 (stream-enumerate-interval 10 100))
(define s2 (stream-enumerate-interval 20 200))
(define s3 (stream-enumerate-interval 30 300))

(define test (stream-map + s1 s2 s3))
(stream-ref test 0)
(stream-ref test 1)
(stream-ref test 2)

3.51

(define (show x)
  (display-line x)
  x)

(define x (stream-map show (stream-enumerate-interval 0 10)))
0
;Value: x
(stream-ref x 5)

1
2
3
4
5

;Value: 5

(stream-ref x 7)

6
7
;Value: 7

It is confusing for me to understand this memo-proc function. All the delayed functions are cached after the first running.

3.52

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
; sum = 1

(define y (stream-filter even? seq))
; sum = 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
; sum = 10

(stream-ref y 7)
;Value: 136

(display-stream z)
; 10
; 15
; 45
; 55
; 105
; 120
; 190
; 210
; sum = 210

sum acts as a global value, which is a bad idea in the stream. When the delay is memorized, seq is the same no matter how many times it is called.

If the non-memorized version is used, then seq would have different result because of the sharing sum.

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
;seq=(1, (accum 2), (accum 3)...(accum 20))
;sum=1

(define y (stream-filter even? seq))
;y=(6, (stream-filter even? ((accum 4), (accum 5), ...)))
;sum=6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
;z=(15, (stream-filter (lambda (x) (...)) ((accum 5) ...)))
;sum=15

(stream-ref y 7)
;y=(6, 24, 30, 54,...)

3.53

(1 2 4 8 16 32 …)

3.54

(define (mul-streams s1 s2)
  (stream-map * s1 s2))
(define factorials
  (cons-stream 1 (mul-streams
                  factorials
                  (integers-starting-from 2))))

3.55

(define (partial-sum s)
  (cons-stream
    (car s)
    (add-streams
      (stream-cdr s)
      (partial-sum s))))

3.56

(define S
  (cons-stream
   1 (merge (scale-stream S 2)
            (merge (scale-stream S 3)
                   (scale-stream S 5)))))

3.57

memorized version is $O(n)$ while naive version is $O(2^n)$

3.58

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

It is long divide.

3.59

(define (integrate-series s)
  (stream-map / s integers))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))
(define cosine-series
  (cons-stream 1
               (scale-stream
                 (integrate-series sine-series)
                 -1))

3.60

(define (mul-series s1 s2)
  (cons-stream
    (* (stream-car s1) (stream-car s2))
    (add-streams
      (scale-stream
        (stream-cdr s2)
        (stream-car s1))
      (mul-series
        (stream-cdr s1)
        s2))))

(define t
  (add-streams
    (mul-series sine-series sine-series)
    (mul-series cosine-series cosine-series)))

(display-stream t)

$(h1 + tail1) * (h2 + tail2) = h1 * h2 + h1tail2 + tail1(h2+tail2)$

3.61

(define (invert-unit-series s)
  (cons-stream 1
               (scale-stream
                 (mul-series
                   (stream-cdr s)
                   (invert-unit-series s)))))

3.62

(define (div-series num den)
   (let ((den0 (stream-car den)))
      (if (= den-const 0)
        (error "The constant term of the denominator must be nonzero")
        (scale-stream
         (mul-series
          num (invert-unit-series
                (scale-stream den (/ 1 den-const))))
         (/ 1 den-const)))))

The den should be normalized to have the $constant=1$

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-4 »

Hide Comments

comments powered by Disqus
sicp-3-4 - kamelzcs's library

sicp-3-4

Posted on 2015-03-02 01:03:22 +0900 in SICP Lisp

3.39

  1. 101: P1 , P2
  2. 121: P2, P1
  3. 100: P1 computes (* x x), then P2 completes and sets x to 101, then P1 executes the assignment.

3.41

As withdraw and diposit are both single modification operations, it is not necessary to protect the balance value, as it would always be valid.

3.42

It seems both of them would work.

3.43

The sum would be kept just because each account is consistent individually.

3.44

Ben is correct. Exchange requires consitent states for both accounts, while transfer would be fine as long as the sum of two accounts is correct.

3.45

serialized-exchange has locked both accounts, which makes it impossible to run deposit or withdraw.

3.46

If atomic is not guaranteed, then multiple process can gain the same mutex at the same time which would result in wrong result.

3.47

(define (make-semaphore n)
  (let ((the-mutex (make-mutex))
        (count 0))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (the-mutex 'acquire)
             (if (= count n) ; full, have to wait
               (begin
                 (the-mutex 'release)
                 (the-semaphore 'acquire))
               (begin
                 (set! count (+ count 1))
                 (the-mutex 'release))))
            ((eq? m 'release)
             (the-mux 'require)
             (set! count (- count 1))
             (the-mux 'release))))
    the-semaphore))

3.48

(define (make-account-and-serializer balance id)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'id) id)
            ((eq? m 'serializer) balance-serializer)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer))
        (id1 ((account1 'id1)))
        (id2 ((account1 'id2))))
    (if (< id1 id2))
    ((serializer2 (serializer1 exchange))
     account1
     account2)
    ((serializer1 (serializer2 exchange))
     account1
     account2)))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-3-5 »

Hide Comments

comments powered by Disqus
sicp-3-3-5 - kamelzcs's library

sicp-3-3-5

Posted on 2015-03-01 22:37:18 +0900 in SICP Lisp

3.33

(define (average a b c)
  (let ((x (make-connector))
        (y (make-connector)))
    (adder a b x)
    (multiplier c v u)
    (constant 2 v))
  'ok)

3.34

it is only one-directianl computation. Given the value of b, the value of a can not be evaluated, as the multiplier does not know the left two values should be the same.

3.35

(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0 -- SQUARER" (get-value b))
            (set-value! a (sqrt (get-value b)) me))
        (if (has-value? a)
          (set-value! b (square (get-value a)) me))))
  (define (process-forget-value)
    (forget-value! b me)
    (forget-value! a me))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my value)
           (process-new-value))
          (else
            (error "Unkown request  SQUARE" request))))
  (connect a me)
  (connect b me)
  me)

3.37

(define (c- x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

(define (c* x y)
  (let ((z (make-connector)))
    (multiplier x y z)
    z))

(define (c/ x y)
  (let ((z (make-connector)))
    (multiplier y z x)
    z))

(define (cv x)
  (let ((z (make-connector)))
    (constant x z)
    z))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-3-4 »

Hide Comments

comments powered by Disqus
sicp-3-3-4 - kamelzcs's library

sicp-3-3-4

Posted on 2015-02-28 07:36:07 +0900 in SICP Lisp

3.28

(define (or-gate a1 a2 output)
  (define or-action-procedure
    (let ((new-value
            (logical-or (get-signal a1) (get-signal a2))))
      (after-delay or-gate-delay
                   (lambda ()
                     set-signal! output new_value))))
  (add-action! a1 or-action-procedure)
  (add-action! a2 or-action-procedure)
  'ok)

3.29

(define (or-gate a1 a2 output)
  (define (or-action-procedure)
    (let ((not-a1 (make-wire))
          (not-a2 (make-wire))
          (b (make-wire))
          )
      (inverter a1 not-a1)
      (inverter a2 not-a2)
      (and-gate not-a1 not-a2 b)
      (inverter b result)))
  (add-action! a1 or-action-procedure)
  (add-action! a2 or-action-procedure)
  'ok)

2 * inverter + and-gate

3.30

(define (ripple-carry-adder A B S C)
  (let ((c-middle (make-wire)))
    (if (null? (cdr A))
      (set-signal! c-middle 0)
      (ripple-carry-adder (cdr A) (cdr B) (cdr S) c-middle))
    (full-adder (car A) (car B) c-middle (car S) C)))

3.31

After calling it immediatly, the initial value of the circuit is propagated. But there is somoe overhead here, in the and-date function, both a1 and a2 will call the and-function-procedure, there would be two function calls and yield two same results, one of which will be looked over by the set-my-signal function.

3.32

(define (make-wire)
  (let ((signal-value 0) (action-procedures '()))
    (define (set-my-signal! new-value)
      (if (not (= signal-value new-value))
          (begin (set! signal-value new-value)
                 (call-each action-procedures))
          'done))
    (define (accept-action-procedure! proc)
      (set! action-procedures (cons proc action-procedures))
      (proc))
    (define (dispatch m)
      (cond ((eq? m 'get-signal) signal-value)
            ((eq? m 'set-signal!) set-my-signal!)
            ((eq? m 'add-action!) accept-action-procedure!)
            (else (error "Unknown operation -- WIRE" m))))
    dispatch))

(define (and-gate a1 a2 output)
  (define (and-action-procedure)
    (let ((new-value
           (logical-and (get-signal a1) (get-signal a2))))
      (after-delay and-gate-delay
                   (lambda ()
                     (set-signal! output new-value)))))
  (add-action! a1 and-action-procedure)
  (add-action! a2 and-action-procedure)
  'ok)

It is important to note that set-my-value will set the state and push the procedure into the queue of the agenda.

(define a (make-wire))
(define b (make-wire))
(define o (make-wire))
(and-gate a b o)
(propagate)

(set-signal! a 0)
(set-signal! b 1)
(propagate)

(set-signal! a 1)
(set-signal! b 0)
(propagate)

When a changed from 0 to 1, output=1 is pushed to the agenda queue, in the following, when b changed from 1 to 0, output=0 is pushed to the agenda queue.

If FIFO is used in the agenda, the final result would be output=0, otherwise, FILO is used, the final result would be output=1, which is not the correct answer at all!

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-3-3 »

Hide Comments

comments powered by Disqus
sicp-3-3-3 - kamelzcs's library

sicp-3-3-3

Posted on 2015-02-27 19:57:55 +0900 in SICP Lisp

3.24

(define (make-table same-key?)
  (let ((local-table (list '*table*)))
    (define (assoc key records)
      (cond ((null? records) #f)
            ((same-key? key (caar records)) (car records))
            (else (assoc key (cdr records)))))
  (define (lookup key-1 key-2)
    (let ((subtable (assoc key-1 (cdr local-table))))
      (if subtable
        (let ((record (assoc key-2 (cdr subtable))))
          (if record
            (cdr record)
            #f
            ))
        #f)))
  (define (insert! key-1 key-2 value)
    (let ((subtable (assoc key-1 (cdr local-table))))
      (if subtable
        (let ((record (assoc key-2 (cdr subtable))))
          (if record
            (set-cdr! record value)
            (set-cdr! subtable (cons
                                 (cons key-2 value)
                                 (cdr subtable)))))
        (set-cdr! local-table (cons
                                (list key-1
                                      (cons key-2 value))
                                (cdr local-table))))))
  (define (dispatch m)
    (cond ((eq? m 'lookup-proc) lookup)
          ((eq? m 'insert-proc!) insert!)
          (else (error "Unkown operation -- TABLE" m))))
  dispatch))

3.25

(define (fold-left op init seq)
  (define (iter ans res)
    (if (null? res)
      ans
      (iter (op ans (car res)) (cdr res))))
  (iter init seq))

(define (make-table same-key?)
  (define (associate key records)
    (cond ((null? records) #f)
          ((same-key? key (caar records))
           (car records))
           (else
             (associate key (cdr records)))))
  (let ((the-table (list '*table*)))
    (define (lookup keys)
      (define (lookup-record record-list key)
        (if record-list
          (let ((record (associate key record-list)))
            (if record
              (cdr record)
              #f))
          #f))
    (fold-left lookup-record (cdr the-table) keys))
  (define (insert! keys value)
    (define (descend table key)
      (let ((record (associate key (cdr table))))
        (if record
          record
          (let ((new (cons (list key)
                           (cdr table))))
            (set-cdr! table new)
            (car new)))))
    (set-cdr! (fold-left descend the-table keys)
              value))
  (define (dispatch m)
    (cond ((eq? m 'lookup) lookup)
          ((eq? m 'insert!) insert!)
          (else (error "Undefined method" m))))
    dispatch))

(define op-table (make-table eq?))
(define put (op-table 'insert!))
(define get (op-table 'lookup))
(put '(letters a) 97)  ; Two dimensions
(put '(letters b) 98)
(put '(math +) 43)
(put '(math -) 45)
(put '(math *) 42)
(put '(greek majiscule Λ) 923)  ; Three dimensions
(put '(greek miniscule λ) 955)
(put '(min) 42)  ; One dimension
(put '(max) 955)
(get '(min))
(get '(letters b))
(put '(min) 43)  ; update
(get '(min))

This is a hard problem for me, as recursive problem is always hard for me to understand. schemewiki provides a great base for this problem, especially the fold-left is used, which simplifies the logic a lot.

Recursive relies on split the problem into smaller consistently defined subproblems.

((k11
   (k12
     (k13 v1)))
(k21
   (k22
     (k23 v2)))
(k31
   (k32 v3)))

Multi-dimention table looks like this.

3.26

(define (entry tree) (car tree))
(define (entry-key tree) (caar tree))
(define (entry-value tree) (cdar tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)
  (list entry left right))

(define (adjoin-set x set)
  (cond ((null? set)
         (make-tree x '() '()))
        ((= (car x) (entry-key set))
         (set-cdr! (entry set) x))
        ((< (car x) (entry-key set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        (else
          (make-tree (entry set)
                     (left-branch set)
                     (adjoin-set x (right-branch set))
                     ))))

(define (make-table)
  (let ((local-table '()))
    (define (associate key)
      (define (iter tree)
        (cond ((null? tree) #f)
              ((= key (entry-key tree))
               (entry tree))
              ((< key (entry-key tree))
               (iter (left-branch tree)))
              (else
                (iter (right-branch tree)))))
      (iter local-table))
    (define (insert! key value)
      (let ((record (associate key)))
        (if record
          (set-cdr! record value)
          (set! local-table
            (adjoin-set (cons key value) local-table)
            ))))
     (define (dispatch m)
       (cond ((eq? m 'get-proc) associate)
             ((eq? m 'insert-proc) insert!)))
     dispatch))

(define table (make-table))
(define get (table 'get-proc))
(define put (table 'insert-proc))

(put 43 'a)
(put 42 'b)
(get 43)
(get 42)

(put 43 'e)
(get 43)

3.27

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

The key lies in the memo-fib will share the table cache.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-3-2 »

Hide Comments

comments powered by Disqus
sicp-3-3-2 - kamelzcs's library

sicp-3-3-2

Posted on 2015-02-27 00:17:13 +0900 in SICP Lisp

3.21

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
(define (empty-queue? queue) (null? (front-ptr queue)))
(define (make-queue) (cons '() '()))
(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (car (front-ptr queue))))
(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else
           (set-cdr! (rear-ptr queue) new-pair)
           (set-rear-ptr! queue new-pair)
           queue))))
(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        (else
         (set-front-ptr! queue (cdr (front-ptr queue)))
         queue)))

3.22

(define make-queue
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (empty-queue?) (null? front-ptr))
    (define (set-front-ptr! item) (set! front-ptr item))
    (define (set-rear-ptr! item) (set! rear-ptr item))
    (define (front-queue)
      (if (empty-queue?)
        (error "FRONT called with an empty queue")
        (car front-ptr)))
    (define (insert-queue! item)
      (let ((new-pair (cons item '())))
        (cond (empty-queue?
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair))
              (else
                (set-cdr! rear-ptr new-pair)
                (set-rear-ptr! new-pair)))))
    (define (delete-queue!)
      (cond (empty-queue?
             (error "DELETE! called with an empty queue"))
            (else
              (set-front-ptr! (cdr front-ptr)))))
    (define print-queue front-ptr)
    (define (dispatch m) 
      (cond ((eq? m 'empty-queue) empty-queue?) 
            ((eq? m 'front-queue) front-queue) 
            ((eq? m 'insert-queue!) insert-queue!) 
            ((eq? m 'delete-queue!) delete-queue!) 
            ((eq? m 'print-queue) print-queue) 
            (else (error "undefined operation -- QUEUE" m))))
     dispatch))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-3-1 »

Hide Comments

comments powered by Disqus
sicp-3-3-1 - kamelzcs's library

sicp-3-3-1

Posted on 2015-02-26 20:23:25 +0900 in SICP Lisp

3.16

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

(define z3 '(a b c))
(count-pairs z3)

(define z1 '(c))
(define z4
  (list z1 z1))

(define z23
  (cons z1 z1))
(define z7
  (cons z23 z23))


(define zi '(a b c))
(set-cdr! (cddr zi) zi)
(count-pairs zi)

The construct of zi is hard for me. It could be built with the lazy evaluation as well.

3.17

(eq? x y) tests whether x and y are the same object (that is, whether x and y are equal as pointers)

Understanding the pointer is the key to understand sameness and sharing.

(define (count-pairs x)
  (let ((aux '()))
    (define (uncounted? x)
      (if (memq x aux)
        0
        (begin
          (set! aux (cons x aux))
          1)))
    (define (count x)
      (if (not (pair? x))
        0
        (+
          (count (car x))
          (count (cdr x))
          (uncounted? x))))
    (count x)))

3.18

(define (cycle? l)
  (define (detect pair countedList)
    (cond ((not (pair? pair)) #f)
          ((memq pair countedList) #t)
          (else
            (detect (cdr pair) (cons pair countedList)))))
  (detect l '()))

3.19

(define (has_cycle? l)
  (define (iter l r)
    (cond ((eq? l r) #t)
          ((not (pair? r)) #f)
          ((not (pair? (cdr r))) #f)
          (else (iter (cdr l) (cdr (cdr r))))))
  (cond ((not (pair? l)) #f)
        ((not (pair? (cdr l))) #f)
        (else (iter (cdr l) (cdr (cdr l))))))

It is a frequently asked question in a interview. Special attention should be paied to the corner cases.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-2 »

Hide Comments

comments powered by Disqus
sicp-3-2 - kamelzcs's library

sicp-3-2

Posted on 2015-02-26 07:59:06 +0900 in SICP Lisp

In the environment model of evaluation, a procedure is always a pair consisting of some code and a pointer to an environment. Procedures are created in one way only: by evaluating a lambda expression. This produces a procedure whose code is obtained from the text of the lambda expression and whose environment is the environment in which the lambda expression was evaluated to produce the procedure.

Important quote from the SICP text, which is the principle to understand the model part. Lambda expression is the key to create a procedure.

Each procedure contains a environment pointer and a code pointer. When calling a procedure, a new environment is derived from the defining environment with new parameters added in.

Drawing the graphs is time consuming, skip them for now.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-1-2-3-1-3 »

Hide Comments

comments powered by Disqus
sicp-3-1-2-3-1-3 - kamelzcs's library

sicp-3-1-2-3-1-3

Posted on 2015-02-26 01:59:04 +0900 in SICP Lisp

3.5

#lang racket

(define (square x) (* x x))

(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (* (random) range))))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1) (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1) trials-passed))))
  (iter trials 0))

(define (rect-area x1 x2 y1 y2)
  (abs (* (- x2 x1) (- y2 y1))))

(define (estimate-integral P x1 x2 y1 y2 trials)
  (define (test)
    (P (random-in-range x1 x2) (random-in-range y1 y2)))
  (* (monte-carlo trials test)
     (rect-area x1 x2 y1 y2)))

(define (estimate-pi trials)
  (define (P x y)
    (< (+ (square x) (square y)) 1.0))
  (estimate-integral P -1.0 1.0 -1.0 1.0 trials))

(estimate-pi 10000000)

The random function in neil/sicp dialect would only return integer, to return a real number back, I have to rely on the racket dialect.

3.7

(define (make-joint acc acc-pass new-pass)
  (define (dispatch password m)
    (if (eq? password new-pass)
      (acc acc-pass m)
      (error "Bad password" password)))
  dispatch)

3.8

(define f
  (let ((state 0))
    (lambda (x)
      (let ((old-state state))
        (set! state x)
        old-state))))

The key lies in to make a closure and make use of its side effect.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-1-1 »

Hide Comments

comments powered by Disqus
sicp-3-1-1 - kamelzcs's library

sicp-3-1-1

Posted on 2015-02-25 20:47:35 +0900 in SICP Lisp

3.1

(define (make-accumulator initial)
  (let ((accumulate initial))
    (lambda (x)
      (set! accumulate (+ accumulate x))
      accumulate)))

3.2

(define (make-monitored proc)
  (let ((call-times 0))
    (define (dispatch m)
      (cond
        ((eq? m 'how-many-calls?) call-times)
        ((eq? m 'reset-count) (set! call-count 0))
        (else
          (set! call-times (+ 1 call-times))
          (proc m))))
    dispatch))

3.3

(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount) (begin (set! balance (- balance amount)) balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount)) balance)
  (define (dispatch pass m)
    (if (not (eq? pass password))
      (error "Bad password -- " pass)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            (else (error "Unknown request -- MAKE-ACCOUNT" m)))))
  dispatch)

3.4

(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount) (begin (set! balance (- balance amount)) balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount)) balance)
  (define (error-message amount)
    (display 'incorrect-password))
  (let ((incorrect-pass-count 0))
    (define (dispatch pass m)
        (if (not (eq? pass password))
          (begin
            (set! incorrect-pass-count (+ 1 incorrect-pass-count))
            (if (> incorrect-pass-count 7)
              call-the-cops
              error-message))
          (begin
            (set! incorrect-pass-count 0)
            (cond ((eq? m 'withdraw) withdraw)
                            ((eq? m 'deposit) deposit)
                            (else (error "Unknown request -- MAKE-ACCOUNT" m)))))))
  dispatch)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2-5-2 »

Hide Comments

comments powered by Disqus
sicp-2-5-2 - kamelzcs's library

sicp-2-5-2

Posted on 2015-02-25 07:03:37 +0900 in SICP Lisp

2.81

If try to coerce two numbers, it would fall into a infinite loop.

It would show an error message if trying to convert an augument to its own type, which is correct.

2.82

(define (apply-generic op . args)
  (define (apply-generic op args type-list)
    (if (null? type-list)
      (error "No method for types"
             (list op (map type-tag args))))
    (let ((new-args (map (lambda (x)
                           (convert x (car type-list)))
                         args)))
      (let ((new-tags (map type-tag new-args)))
        (let ((proc (get op new-tags)))
          (if proc
            (apply proc (map contents new-args))
            (apply-generic op args (cdr type-list)))))))
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
        (apply proc (map contents args))
        (apply-generic op args type-tags)))))

2.83

(define (raise x) (apply-generic 'raise x))
 (put 'raise 'integer
      (lambda (x) (make-rational x 1)))

 (put 'raise 'rational
      (lambda (x) (make-real (/ (numer x) (denom x)))))

 (put 'raise 'real
          (lambda (x) (make-from-real-imag x 0)))

2.84 ~ 2.97

I decided to skip the above ones just because they are so code intense, maybe I will come back to them in the future.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2-5-1 »

Hide Comments

comments powered by Disqus
sicp-2-5-1 - kamelzcs's library

sicp-2-5-1

Posted on 2015-02-24 21:01:24 +0900 in SICP Lisp

2.77

(apply-generic 'magnitude '(complex rectangular 3 4))
-->
((get 'magnitude '(complex)) '(rectangular 3 4))
-->
(magnitude '(rectangular 3 4))
-->
(apply-generic 'magnitude '(rectangular 3 4))
-->
((get 'magnitude '(rectangular)) (3 4))
-->
(magnitude (3 4))

2.78

(define (attach-tag type-tag contents)
   (if (number? contents)
       contents
       (cons type-tag contents)))

 (define (type-tag datum)
   (cond ((number? datum) 'scheme-number)
         ((pair? datum) (car datum))
         (else (error "Bad taged datum -- TYPE-TAG" datum))))

 (define (contents datum)
   (cond ((number? datum) datum)
         ((pair? datum) (cdr datum))
         (else (error "Bad taged datum -- CONTENTS" datum))))

2.79

(define (equ? x y)
  (apply-generic 'equ ? x y))

(put 'equ? '(scheme-number scheme-number) =)
(put 'equ? '(rational rational) equ-rat?)
(define (equ-rat? x y)
  (and (= (numer x) (numer y))
       (= (denom x) (denom y)))

(put 'equ? '(complex complex) equ-complex?)
(define (equ-complex? x y)
  (and (= (real-part x) (real-part y))
       (= (imag-part x) (imag-part y))))

The tag of the number should be managed separately in the procedures.

2.80

(define (=zero? x) (apply-generic '=zero? x))
(put '=zero? 'scheme-number (lambda (x) (= x 0)))
(put '=zero? 'rational-number
        (lambda (x) (= (number x) 0)))
(put '=zero? 'complex-number
        (lambda (x) (= (magnitude x) 0)))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2-4 »

Hide Comments

comments powered by Disqus
sicp-2-4 - kamelzcs's library

sicp-2-4

Posted on 2015-02-24 06:45:38 +0900 in SICP Lisp

2.73

(define global-array '())

(define (make-entry k v) (list k v))
(define (key entry) (car entry))
(define (value entry) (cadr entry))

(define (put op type item)
  (define (put-helper k array)
    (cond ((null? array) (list(make-entry k item)))
          ((equal? (key (car array)) k) array)
          (else (cons (car array) (put-helper k (cdr array))))))
  (set! global-array (put-helper (list op type) global-array)))

(define (get op type)
  (define (get-helper k array)
    (cond ((null? array) #f)
          ((equal? (key (car array)) k) (value (car array)))
          (else (get-helper k (cdr array)))))
  (get-helper (list op type) global-array))

(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

(define (attach-tag type-tag contents)
  (if (= type-tag 'scheme-number)
      contents
      (cons type-tag contents)))
(define (type-tag datum)
  (cond ((number? datum) 'scheme-number)
        ((pair? datum) (car datum))
        (else (error "Bad tagged datum -- TYPE-TAG" datum))))
(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Bad tagged datum -- CONTENTS" datum))))
(define (install-deriv-package)
  (define (=number? exp num)
    (and (number? exp) (= exp num)))

  (define (make-sum a1 a2)
    (cond ((=number? a1 0) a2)
          ((=number? a2 0) a1)
          ((and (number? a1) (number? a2)) (+ a1 a2))
          (else (list '+ a1 a2))))
  (define (addend data) (car data))
  (define (augend data) (cadr data))
  (define (deriv-sum data var)
    (make-sum (deriv (addend data) var)
              (deriv (augend data) var)))

  (define (make-product m1 m2)
    (cond ((or (=number? m1 0) (=number? m2 0)) 0)
          ((=number? m1 1) m2)
          ((=number? m2 1) m1)
          ((and (number? m1) (number? m2)) (* m1 m2))
          (else (list '* m1 m2))))
  (define (multiplier data) (car data))
  (define (multiplicand data) (cadr data))
  (define (deriv-product data var)
    (make-sum
     (make-product (multiplier data)
                   (deriv (multiplicand data) var))
     (make-product (deriv (multiplier data) var)
                   (multiplicand data))))

  (define (make-exponentiation base exp)
    (cond ((=number? exp 0) 1)
          ((=number? exp 1) base)
          (else (list '** base exp))))
  (define (base data) (car data))
  (define (exponent data) (cadr data))
  (define (deriv-exponentation data var)
    (make-product
     (exponent data)
     (make-product
      (make-exponentiation (base data)
                           (make-sum (exponent data) (- 1)))
      (deriv (base data) var))))

  (put 'deriv '+ deriv-sum)
  (put 'deriv '* deriv-product)
  (put 'deriv '** deriv-exponentation)
  'done)

(install-deriv-package)
(deriv '(** (+ (** x 2) 1) 2) 'x)

put and get is from stackoverflow.

2.75

(define (make-from-mag-ang r a)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          (else
           (error "Unknown op -- MAKE-FROM-MAG-ANG" op))))
  dispatch)

2.76

Message passing style is more flexible compared with data driven style, which is self contained. But message passing suffers from the only generic procedures of one argument.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2-3-4 »

Hide Comments

comments powered by Disqus
sicp-2-3-4 - kamelzcs's library

sicp-2-3-4

Posted on 2015-02-23 02:20:49 +0900 in SICP Lisp

2.67

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))
(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))
(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))
(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)    ; symbol
                               (cadr pair))  ; frequency
                    (make-leaf-set (cdr pairs))))))
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))
'(0 1 1 0 0 1 0 1 0 1 1 1 0)
'(A D     A B   B   C     A)

2.68

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (encode-symbol symbol tree)
  (cond ((not (memq symbol (symbols tree)))
         (error "bad symbol -- encode-symbol" symbol))
        ((leaf? tree)
         '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0
               (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1
               (encode-symbol symbol (right-branch tree))))))

2.69

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge leaves)
  (if (null? (cdr leaves))
    (car leaves)
    (successive-merge
      (adjoin-set (make-code-tree
                    (car leaves)
                    (cadr leaves))
                  (cddr leaves)))))

2.70

(define lyric-tree
  (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2)
                           (NA 16) (SHA 3) (YIP 9) (WAH 1))))

(length (encode '(GET A JOB
          SHA NA NA NA NA NA NA NA NA
          GET A JOB
          SHA NA NA NA NA NA NA NA NA
          WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
          SHA BOOM)
        lyric-tree))

It take 84 bits compared with the 108 bits in fixed-length.

2.71

It takes 1 bit to encode the most frequent bit and n - 1 bits to encode the least frequent bit.

2.72

If the encode uses an unordered set to keep its symbols, it would take about $O(n)$ to encode the most frequent symbol and to encode the least frequent symbol.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.3.3 »

Hide Comments

comments powered by Disqus
sicp-2.3.3 - kamelzcs's library

sicp-2.3.3

Posted on 2015-02-22 23:54:30 +0900 in SICP Lisp

2.59

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else
          (cons (car set1)
                (union-set (cdr set1)
                           set2)))))

2.60

(define (adjoin-set x set)
   (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

adjoin-set goes from $O(n)$ to $O(1)$

union-set goes from $O(n^2)$ to $O(n)$

2.61

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< x (car set)) (cons x set))
        ((= x (car set)) set)
        ((> x (car set)) (cons (car set)
                               (adjoin-set x (cdr set))))))

2.62

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
          (let* ([x1 (car set1)] [x2 (car set2)])
            (cond ((< x1 x2)
                   (cons x1
                         (union-set (cdr set1) set2)))
                  ((= x1 x2)
                   (cons x1
                         (union-set (cdr set1) (cdr set2))))
                  (else
                    (cons x2
                          (union-set set1 (cdr set2)))))))))

2.63

It would make no difference on the final result, both of them are in order traverse. But there is something tricky on the time complexity1.

append is much more expensive than cons.

Let $T(n)$ be the time complexity for a balanced tree of $n$ nodes.

For tree->list-1:

For tree->list-2:

2.64

The analysis of time complexity is similar to the 2.63, which is $O(nlog n)$.

2.65

Use tree-list from 2.63 and list-tree to convert bidirectional.

 (define (union-set tree1 tree2)
   (list->tree (union-set-list (tree->list tree1)
                               (tree->list tree2))))

 (define (intersection-set tree1 tree2)
   (list->tree (intersection-set-list (tree->list tree1)
                                      (tree->list tree2))))

2.66

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
    #f
    (let ([record (entry set-of-records)])
      (cond ((= given-key (key record)) record)
            ((< given-key (key record))
             (lookup given-key
                     (left-branch set-of-records)))
            ((> given-key (key record))
             (lookup given-key 
                     (right-branch set-of-records)))))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.3.2 »

Hide Comments

comments powered by Disqus
sicp-2.3.2 - kamelzcs's library

sicp-2.3.2

Posted on 2015-02-21 07:41:20 +0900 in SICP Lisp

2.56

(print-as-expression #f)

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))
(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
           (exponent exp)
           (make-product
             (make-exponentiation
               (base exp)
               (make-sum (exponent exp) (- 1)))
             (deriv (base exp) var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (make-exponentiation base exp)
  (cond ((=number? exp 0) 1)
        ((=number? exp 1) base)
        (else (list '** base exp))))

(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (base e) (cadr e))

(define (exponent e) (caddr e))

The tricky part to use all the high level function such as make-sum, as the exp could be a expression as well.

2.57

(define (augend s)
  (if (null? cdddr s)
    (caddr s)
    (cons '+ (cddr s))))

2.58

Skipped

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.3.1-2.3.2 »

Hide Comments

comments powered by Disqus
sicp-2.3.1-2.3.2 - kamelzcs's library

sicp-2.3.1-2.3.2

Posted on 2015-02-20 19:41:41 +0900 in SICP Lisp

2.54

(define (equal? a b)
  (cond ((and (pair? a) (pair? b))
         (and (equal? (car a) (car b))
              (equal? (cdr a) (cdr b))))
        ((and (not (pair? a)) (not (pair? b)))
         (eq? a b))
        (else #f)))

2.55

(car ''abracadabra)
-->
(car (quote (quote abracadabra)))
-->
'quote
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.2.4 »

Hide Comments

comments powered by Disqus
sicp-2.2.4 - kamelzcs's library

sicp-2.2.4

Posted on 2015-02-20 07:20:40 +0900 in SICP Lisp

package used

Drracket picture language is used.

#lang racket
(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

2.44

(define (up-split painter n)
  (if (= n 0)
    painter
    (let ((smaller (up-split painter (- n 1))))
      (below painter (beside smaller smaller)))))

2.45

(define (split op1 op2)
  (lambda (painter n)
    (if (= n 0)
        painter
        (let ((smaller ((split op1 op2) painter (- n 1))))
          (op1 painter (op2 smaller smaller))))))

2.46

(define (make-vect x y)
   (cons x y))

(define (xcor-vect v)
   (car v))

(define (ycor-vect v)
   (cdr v))

(define (add-vect u v)
   (make-vect
     (+ (xcor-vect u) (xcor-vect v))
     (+ (ycor-vect u) (ycor-vect v))))

(define (sub-vect u v)
   (make-vect
     (- (xcor-vect u) (xcor-vect v))
     (- (ycor-vect u) (ycor-vect v))))

(define (scale-vect s v)
   (make-vect
     (* s (xcor-vect v))
     (* s (ycor-vect v))))

2.47

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (origin-frame frame)
  (car frame))

(define (edge1-frame frame)
  (cadr frame))

(define (edge2-frame frame)
  (caddr frame))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

(define (origin-frame frame)
  (car frame))

(define (edge1-frame frame)
  (cadr frame))

(define (edge2-frame frame)
  (cddr frame))

2.48

(define (make-segment u v)
  (cons u v))

(define (start-segment segment)
  (car segment))

(define (end-segment segment)
  (cdr segment))

2.49

(define (draw-outline frame)
  ((segments->painter
    (list (make-segment (make-vect 0 0)
                        (make-vect 1 0))
          (make-segment (make-vect 1 0)
                        (make-vect 1 1))
          (make-segment (make-vect 1 1)
                        (make-vect 0 1))
          (make-segment (make-vect 0 1)
                        (make-vect 0 0)))
    frame)))

(define (draw-X frame)
  ((segments->painter
    (list (make-segment (make-vect 0 0)
                        (make-vect 1 1))
          (make-segment (make-vect 1 0)
                        (make-vect 0 1))))
   frame))

(define (draw-diamond frame)
  ((segments->painter
    (list (make-segment (make-vect 0.5 0.0)
                        (make-vect 1.0 0.5))
          (make-segment (make-vect 1.0 0.5)
                        (make-vect 0.5 1.0))
          (make-segment (make-vect 0.5 1.0)
                        (make-vect 0.0 0.5))
          (make-segment (make-vect 0.0 0.5)
                        (make-vect 0.5 0.0))))

2.50

(define (flip-horiz painter)
  (transform-painter painter
                     (make-vect 1 0)
                     (make-vect 0 0)
                     (make-vect 1 1)))

(define (rotate180 painter)
  (transform-painter painter
                     (make-vect 1 1)
                     (make-vect 0 1)
                     (make-vect 1 0)))

(define (rotate270 painter)
  (transform-painter painter
                     (make-vect 0 1)
                     (make-vect 0 0)
                     (make-vect 1 1)))

2.51

Hint from the wqzhang, which is very elegant.

(define (below painter1 painter2)
  (rotate90 (beside (rotate270 painter1)
                    (rotate270 painter2))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.2.3 »

Hide Comments

comments powered by Disqus
sicp-2.2.3 - kamelzcs's library

sicp-2.2.3

Posted on 2015-02-18 19:31:27 +0900 in SICP Lisp

2.33

(define (accumulate op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))

(define (map p sequence)
   (accumulate (lambda (x y) (cons (p x) y)) null sequence))

(define (square x) (* x x))

(map square '(1 2 3))

(define (append seq1 seq2)
   (accumulate cons seq2 seq1))

(append (list 1 2 3) (list 4 5 6))

(define (length sequence)
   (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

(length '(1 2 3))

The append is kind of tricky to me at first glance. Just remaind me this equition: cons 1 (list 2 3) = (list 1 2 3)

2.34

(define (horner-eval x coefficient-sequence)
   (accumulate (lambda (this-coeff higher-terms)
                 (+ this-coeff
                    (* x higher-terms)))
               0
               coefficient-sequence))

(horner-eval 2 (list 1 3 0 5 0 1))

2.35

(define (count-leaves t)
   (accumulate + 0 (map
                     (lambda (x)
                       (if (not (pair? x))
                         1
                         (count-leaves x)))
                     t)))

This is the most elegant way, which flats the tree structure recursively.

2.36

(define (accumulate-n op init seqs)
   (if (null? (car seqs))
       null
       (cons (accumulate op init
                         (map (lambda (x)
                                (car x))
                              seqs))
             (accumulate-n op init
                           (map (lambda (x)
                                  (cdr x))
                                seqs)))))

(accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

2.37

(define (dot-product v w)
   (accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
   (map (lambda (row)
          (dot-product v row)) m))

(define m0 '((1 2 3 4) (4 5 6 6) (6 7 8 9)))
(matrix-*-vector m0 '( 2 1 4 5))

(define (transpose mat)
   (accumulate-n cons null  mat))

(transpose m0)

(define (matrix-*-matrix m n)
   (let ([cols (transpose n)])
      (map (lambda(v) (matrix-*-vector cols v)) m)))

(matrix-*-matrix m0 (transpose m0))

2.38

(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

(define (fold-left op initial sequence)
   (define (iter result rest)
     (if (null? rest)
         result
         (iter (op result (car rest))
               (cdr rest))))
   (iter initial sequence))

(fold-right / 1 (list 1 2 3))
3/2
(fold-left / 1 (list 1 2 3))
1/6
(fold-right list null (list 1 2 3))
(1 (2 (3 ())))
(fold-left list null (list 1 2 3))
(((() 1) 2) 3)

Both associativity and commutativity. That is

(op a b) = (op b a) and (op (op a b) c) = (op a (op b c))

2.39

(define (reverse sequence)
  (fold-right (lambda (x y)
                (append y (list x)))
              null
              sequence))

(reverse (list 1 2 3 4))

(define (reverse sequence)
  (fold-left (lambda (x y)
                (cons y  x))
              null
              sequence))

(reverse (list 1 2 3 4))

2.40

(define (unique-pairs n)
  (flatmap (lambda (i)
             (map (lambda (j) (list i j))
                  (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

(define (prime-sum-pairs n)
   (map make-pair-sum
        (filter prime-sum?
                (unique-pairs n))))

2.41

(define (unique-triples n)
  (flatmap (lambda (i)
             (flatmap (lambda (j)
                        (map
                          (lambda (k) (list i j k))
                          (enumerate-interval 1 (- j 1))))
                      (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

(define (equal-sum? s)
  (lambda (lst)
    (= s (accumulate + 0 lst))))

2.42

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(define empty-board '())

(define (adjoin-position row k rest-of-queens)
  (append rest-of-queens (list (list row k))))

(define (last l)
    (cond ((null? (cdr l)) (car l))
          (else (last (cdr l)))))

(define (safe? k positions)
  (define (attack? q1 q2)
    (and (not (= (car q1) (car q2)))
         (not (= (abs (- (car q1) (car q2)))
                 (abs (-  (cadr q1)(cadr q2)))))))

  (let ((new-queen (last positions)))
    (define (check i positions)
      (cond ((= i k) true)
            ((attack? (car positions) new-queen)
             (check (+ i 1) (cdr positions)))
            (else false)))
    (check 1 positions)))

summary

The key idea to understand map, flatmap is to relate it with Category Theory. To think about something more abstractly would help a lot in understanding concrete concepts. Knowing HOW is the key to finish something, but WHY is the key to master something.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2-2-2 »

Hide Comments

comments powered by Disqus
sicp-2-2-2 - kamelzcs's library

sicp-2-2-2

Posted on 2015-02-17 20:56:36 +0900 in SICP Lisp

2.24

The interpreter would show (1 (2 (3 4))).

2.25

(cadr (caddr '(1 3 (5 7) 9)))
(caar '((7)))
(cadr (cadr (cadr (cadr (cadr (cadr '(1 (2 (3 (4 (5 (6 7))))))))))))

2.26

(define x (list 1 2 3))
(define y (list 4 5 6))

(append x y)
->
(1 2 3 4 5 6)

(cons x y)
->
((1 2 3) 4 5 6)

(list x y)
->
((1 2 3) (4 5 6))

2.27

(define (deep-reverse items)
  (cond ((pair? items)
         (if (pair? (car items))
           (append
             (deep-reverse (cdr items))
             (list (deep-reverse (car items))))
           (append (deep-reverse (cdr items))
                   (deep-reverse (car items)))))
        (else
          (if (null? items)
            null
            (list items)))))

2.28

(define (deep-reverse items)
  (cond ((pair? items)
         (if (pair? (car items))
           (append
             (deep-reverse (cdr items))
             (list (deep-reverse (car items))))
           (append (deep-reverse (cdr items))
                   (deep-reverse (car items)))))
        (else
          (if (null? items)
            null
            (list items)))))
(define (fringe tree)
  (cond ((pair? tree)
         (append (fringe (car tree))
                 (fringe (cdr tree))))
        (else
          (if (null? tree)
            null
            (list tree)))))

2.29

(define (make-mobile left right)
   (list left right))

(define (make-branch length structure)
   (list length structure))

(define (left-branch mobile)
   (car mobile))

(define (right-branch mobile)
   (cadr mobile))

(define (branch-length branch)
   (car branch))

(define (branch-structure branch)
   (cadr branch))

(define (total-weight mobile)
   (+ (branch-weight (left-branch mobile))
      (branch-weight (right-branch mobile))))

(define (branch-weight branch)
  (let ([structure (branch-structure branch)])
    (if (pair? structure)
      (total-weight structure)
      structure)))

(define (balanced? mobile)
  (if (pair? mobile)
    (let* ([left (left-branch mobile)]
          [right (right-branch mobile)]
          [left-mobile (branch-structure left)]
          [right-mobile (branch-structure right)])
      (and
        (= (*
             (branch-length left)
             (if (pair? left-mobile)
               (total-weight left-mobile)
               left-mobile))
           (*
             (branch-length right)
             (if (pair? right-mobile)
              (total-weight right-mobile)
              right-mobile)))
        (balanced? left-mobile)
        (balanced? right-mobile)))
    #t))

2.30

(define (scale-tree tree factor)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree factor))
         (else (cons (scale-tree (car tree) factor)
                     (scale-tree (cdr tree) factor)))))

(define (scale-tree tree factor)
   (map (lambda (sub-tree)
          (if (pair? sub-tree)
              (scale-tree sub-tree factor)
              (* sub-tree factor)))
        tree))

(define (square-tree tree)
   (cond ((null? tree) null)
         ((not (pair? tree)) (* tree tree))
         (else (cons (square-tree (car tree))
                     (square-tree (cdr tree))))))

(define (square-tree tree)
   (map (lambda (sub-tree)
          (if (pair? sub-tree)
              (square-tree sub-tree)
              (* sub-tree sub-tree)))
        tree))

2.31

(define (tree-map f tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (f tree))
        (else (cons (tree-map f (car tree))
                    (tree-map f (cdr tree))))))

(define (tree-map f tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree) (tree-map f sub-tree) (f sub-tree)))
       tree))

2.32

(define (subsets s)
  (if (null? s)
      (list null)
      (let ([rest (subsets (cdr s))])
        (append rest
                (map
                  (lambda (x)
                    (append (list (car s)) x))
                  rest)))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.2.1 »

Hide Comments

comments powered by Disqus
sicp-2.2.1 - kamelzcs's library

sicp-2.2.1

Posted on 2015-02-17 07:42:44 +0900 in SICP Lisp

2.17

(define (last-pair lst)
  (let ([second (cdr lst)])
    (if (null? second)
      (car lst)
      (last-pair second))))

2.18

(define (append list1 list2)
   (if (null? list1)
       list2
       (cons (car list1) (append (cdr list1) list2))))

(define (reverse lst)
  (if (null? lst)
    lst
    (append
      (reverse (cdr lst))
      (list (car lst)))))

2.19

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))
(define (no-more? coin-values)
  (null? coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (first-denomination coin-values)
  (car coin-values))

As this procedure does not rely not on the order, it would not affect the final answer.

2.20

(define (same-parity a . z)
  (define (iter f left)
    (if (null? left)
      left
      (let* ([first (car left)]
            [second (cdr left)]
            [temp (iter f second)])
        (if (f first)
          (cons first temp)
          temp))))
  (iter
    (lambda (x) (= (remainder a 2) (remainder x 2)))
    (cons a z)))

2.21

(define (square x) (* x x))

(define (square-list items)
   (if (null? items)
       null
       (cons (square (car items))
             (square-list (cdr items)))))

(define (square-list items)
   (map square items))

2.22

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (append answer
                       (list (square (car things)))))))
   (iter items null))

The correct way is to use append to add it into the last posision of the nested cons.

2.23

(define (for-each proc items)
  (cond
    ((null? items) #t)
    (else (proc (car items))
          (for-each proc (cdr items)))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.1.4 »

Hide Comments

comments powered by Disqus
sicp-2.1.4 - kamelzcs's library

sicp-2.1.4

Posted on 2015-02-17 06:45:26 +0900 in SICP Lisp

2.7

(define (add-interval x y)
   (make-interval (+ (lower-bound x) (lower-bound y))
                  (+ (upper-bound x) (upper-bound y))))

(define (mul-interval x y)
   (let ((p1 (* (lower-bound x) (lower-bound y)))
         (p2 (* (lower-bound x) (upper-bound y)))
         (p3 (* (upper-bound x) (lower-bound y)))
         (p4 (* (upper-bound x) (upper-bound y))))
     (make-interval (min p1 p2 p3 p4)
                    (max p1 p2 p3 p4))))

(define (div-interval x y)
   (mul-interval x
                 (make-interval (/ 1.0 (upper-bound y))
                                (/ 1.0 (lower-bound y)))))

(define (make-interval a b) (cons a b))

(define upper-bound cdr)

(define lower-bound car)

2.8

(define (sub-interval x y)
   (make-interval (- (lower-bound x) (lower-bound y))
                  (- (upper-bound x) (upper-bound y))))

2.10

(define (span-zero? interval)
  (and (>= (upper-bound interval) 0)
           (<= (lower-bound interval) 0)))

(define (div-interval x y)
  (if (span-zero? y)
    (error "divides zero")
    (mul-interval x
                 (make-interval (/ 1.0 (upper-bound y))
                                (/ 1.0 (lower-bound y))))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-2.1.1-2.1.3 »

Hide Comments

comments powered by Disqus
sicp-2.1.1-2.1.3 - kamelzcs's library

sicp-2.1.1-2.1.3

Posted on 2015-02-16 19:31:58 +0900 in SICP Lisp

2.1

(define (number x) (car x))
(define (denom x) (cdr x))

(define (make-rat n d)
  (let ((g (gcd n d)))
    (if (> d 0)
      (cons (/ n g) (/ d g))
      (cons (/ (- n) g) (/ (- d) g)))))

(define (print-rat x)
  (newline)
  (display (number x))
  (display "/")
  (display (denom x)))

2.2

(define (print-point p)
   (newline)
   (display "(")
   (display (x-point p))
   (display ",")
   (display (y-point p))
   (display ")"))

(define (make-segment a b) (cons a b))

(define (start-segment s) (car s))
(define (end-segment s) (cdr s))

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

(define (midpoint-segment s)
  (make-point
    (/
      (+
        (x-point (start-segment s))
        (x-point (end-segment s)))
      2)
    (/
      (+
        (y-point (start-segment s))
        (y-point (end-segment s)))
      2)))

2.3

;define rectangle using two points
(define (make-rec a b) (cons a b))

(define (rect-width r)
  (abs (-
         (x-point (car r))
         (x-point (cdr r)))))

(define (rect-height r)
  (abs (-
         (y-point (car r))
         (y-point (cdr r)))))

(define (rect-perimeter r)
   (* 2 (+ (rect-width r) (rect-height r))))

(define (rect-area r)
   (* (rect-width r) (rect-height r)))

;define rectangle using base point, width and height
(define (make-rect p w h) (cons p (cons w h)))

(define (rect-width r)
   (car (cdr r)))

(define (rect-height r)
   (cdr (cdr r)))

2.4

Lambda is the ultimate way to represent everyting.

(define (proc-cons x y)
  (lambda (m) (m x y)))

(define (proc-car z)
  (z (lambda (p q) p)))

(define (proc-cdr z)
  (z (lambda (p q) q)))

2.5

(define (math-cons a b)
  (* (expt 2 a)
     (expt 3 b)))

(define (math-car s)
  (get-degree s 2))

(define (math-cdr s)
  (get-degree s 3))

2.6

Quote from wiki:

Church numerals are the representations of natural numbers under Church encoding. The higher-order function that represents natural number n is a function that maps any function f to its n-fold composition.

To make it more interesting, church-multi method is added in as well.

Lambda calculas is really powerful.

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
   (lambda (f) (lambda (x) (f ((n f) x)))))

(define one
   (lambda (f) (lambda (x) (f x))))

(define two
   (lambda (f) (lambda (x) (f (f x)))))

(define (church-add a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))

(define (church-multi a b)
  (lambda (f) (lambda (x) ((a (b f)) x))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 1.3.4 »

Hide Comments

comments powered by Disqus
1.3.4 - kamelzcs's library

1.3.4

Posted on 2015-02-16 00:39:53 +0900 in SICP Lisp

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the ``rights and privileges’’ of first-class elements are:

  • They may be named by variables.
  • They may be passed as arguments to procedures.
  • They may be returned as the results of procedures.
  • They may be included in data structures.

1.40

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define dx 0.00001)
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (square x) (* x x))

(define (cube x) (* x x x))

(define (cubic a b c)
  (lambda (x)
    (+ (cube x)
       (* a (square x))
       (* b x)
       c)))

-> (newtons-method (cubic 8 16 10) 1)
-5.3652300134140924

1.41

(define (double f)
  (lambda (x) (f (f x))))

(define (inc x) (+ x 1))

-> ((double inc) 1)
3

-> (((double (double double)) inc) 5)
21

It increases $2^2^2$.

1.42

(define (compose f g)
 (lambda (x) (f (g x))))

1.43

(define (repeated f x)
  (if (= x 1)
      f
      (compose f (repeated f (- x 1)))))

1.44

(define (smooth f dx)
  (lambda (x)
    (/ (+ (f x)
          (f (+ x dx))
          (f (- x dx)))
       3)))

(define (n-fold-smooth f dx n)
  (repeated (smooth f dx) n))

1.46

(define (iterative-improve good-enough? improve)
   (define (iter guess)
     (if (good-enough? guess)
         guess
         (iter (improve guess))))
   iter)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP 1.3.2-1.3.3 »

Hide Comments

comments powered by Disqus
SICP 1.3.2-1.3.3 - kamelzcs's library

SICP 1.3.2-1.3.3

Posted on 2015-02-15 20:13:00 +0900 in SICP Lisp

1.34

(define (f g) (g 2))

(f f)
-->
(f 2)
-->
(2 2)

1.35

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

1.36

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess tried)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          (begin
            (display (+ tried 1))
            (newline)
            next)
          (try next (+ tried 1)))))
  (try first-guess 1))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)

(define (average x y)
  (/ (+ x y) 2))

(fixed-point (lambda (x) (average x
                                  (/ (log 1000) (log x)))) 2.0)

If order to display the iterate numbers, a new parameter tried is added in. A new syntax begin is used in order to run multiple commands sequencely, which will return the last expression’s value as the result.

The simple version will run 35 times, while the average version will only run 10 times.

1.37

(define (cont-frac n d k)
  (define (iter x)
    (if (< x k)
      (/ (n x)
         (+ (d x)
            (iter (+ x 1))))
      (/ (n x)
         (d x))))
  (iter 1))

(define (cont-frac-iter n d k)
  (define (iter k result)
    (if (= k 0)
      result
      (iter (- k 1)
            (+ (d k)
               (/ (n k)
                  result)))))
  (iter (- k 1) (/ (n k)
                   (d k))))

1.38

The key lies in finding out a math expression for

1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8,...

(define (d i)
  (if (not (= 0
              (remainder (+ i 1) 3)))
    1
    (* 2
       (/ (+ i 1)
          3))))

(define euler-e
  (+ 2 (cont-frac (lambda (x) 1.0) d 10)))

1.39

(define (tan-cf x k)
  (cont-frac
    (lambda (a) (if (= a 1)
                  x
                  (- (square x))))
    (lambda (a) (- (* 2 a) 1))
    k))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-1.31 »

Hide Comments

comments powered by Disqus
sicp-1.31 - kamelzcs's library

sicp-1.31

Posted on 2015-02-14 08:22:48 +0900 in SICP Lisp

1.29

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(define (cube x) (* x x x))

(integral cube 0 1 0.01)

(define (simpson-integral f a b n)
  (define h (/ (- b a) n))
  (define (next a) (+ a 1))
  (define (current k) (+ a
                         (* k h)))
  (define (simpson-term x)
    (define point (current x))
    (cond ((or (= x 0) (= x n)) (f point))
          ((even? x) (* 2
                        (f point)))
          (else (* 4
                   (f point)))))
  (* h
     (/ (sum simpson-term 0 next n)
        3)))

1.30

(define (sum-iter term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a) (+ result (term a)))))
  (iter a 0))

1.31

(define (pi-term a)
  (define norm (+ 1
                  (* 2 a)))
  (*
    (/ (-
         (square norm)
         1)
       (square norm))))

(define (wallis-pi n)
  (* 4.0
     (product pi-term 1 inc n)))

(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a) (* result (term a)))))
  (iter a 1))

1.32

(define (accumulate combiner null-value term a next b)
  (if (> a b) null-value
    (combiner (term a)
              (accumulate combiner null-value term (next a) next b))))

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b) result
      (iter (next a) (combiner result (term a)))))
  (iter a null-value))

1.33

(define (filtered-accumulate combiner null-value term a next b filter)
  (if (> a b) null-value
    (if (filter a)
      (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter))
      (filtered-accumulate combiner null-value term (next a) next b filter))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-126 »

Hide Comments

comments powered by Disqus
sicp-126 - kamelzcs's library

sicp-126

Posted on 2015-02-13 19:50:38 +0900 in SICP Lisp

1.21

(define (square x) (* x x))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))

199 and 1999 are primes, 19999’s smallest divisor is 7

1.22

(define (square x) (* x x))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder
           (square (expomod base (/ exp 2) m))
           m))
        (else
          (remainder
            (* base (expmod base (- exp 1) m))
            m))))
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (timed-prime-test n)
   (newline)
   (display n)
   (start-prime-test n (runtime))

(define (start-prime-test n start-time)
   (cond ((prime? n)
          (report-prime (- (runtime) start-time)))))

(define (report-prime elapsed-time)
   (display " *** ")
   (display elapsed-time))

(define (prime? n)
   (= n (smallest-divisor n)))

(define (search-for-primes start end)
  (if (even? start) (search-for-primes (+ start 1) end)
    (cond ((<= start end)
           (timed-prime-test start) (search-for-primes (+ start 2) end)))))

The tricky part is how to run evaluate expressions sequencely. According to cond expressio, the then-bodys are evaluated in order and the results of the last then body provide the result for the whole cond form.

1.26

(define (expmod base exp m)
   (cond ((= exp 0) 1)
         ((even? exp)
          (remainder (* (expmod base (/ exp 2) m)
                        (expmod base (/ exp 2) m))
                     m))
         (else
          (remainder (* base (expmod base (- exp 1) m))
                     m))))

The time complexity of this code is $\sum_{i=0}^{log_n} 2^n = O(n)$

1.27

(define (fixed-fermat-test n a)
  (= (expmod a n n) a))

(define (fermat-full n)
  (define (iter a)
    (cond ((= a 1) #t)
          ((not (fixed-fermat-test n a)) #f)
          (else (iter (- a 1)))))
  (iter (- n 1)))

1.28

(define (MR-expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let* ([part (expmod base (/ exp 2) m)]
                [ans (remainder (square part) m)])
           (if (and (not (or (= part 1) (= part (- m 1))))
                    (= ans 1))
             0
             ans)))
        (else
          (remainder
            (* base (expmod base (- exp 1) m))
            m))))

(define (MR-test n)
  (define (try-it a)
    (= (MR-expmod a (- n 1) n) 1))
  (try-it (+ 2 (random (- n 2)))))

Used let* to deal with the local variable.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-124-125 »

Hide Comments

comments powered by Disqus
sicp-124-125 - kamelzcs's library

sicp-124-125

Posted on 2015-02-12 23:17:32 +0900 in SICP Lisp

1.16

#lang planet neil/sicp

 (define (square x) (* x x))

(define (fast-expt b n)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n) (iter a (square b) (/ n 2)))
          (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

1.18

(define (multi a b)
  (define (fast-multi-iter x y n)
    (cond ((= n 0) x)
          ((even? n) (fast-multi-iter x (double y) (/ n 2)))
          (else (fast-multi-iter (+ x y) y (- n 1)))))
  (fast-multi-iter 0 a b))

1.20

Applicative order:

gcd(206, 40)
gcd(40, remainder(206, 40)) ;1
gcd(6, remainder(40, 6))   ;2
gcd(4, remainder(6, 4))  ;3
gcd(2, remainder(4, 2))  ;4

For normal order, the remainder function is not calculated instantly. It is calculated when it is necessary. It is passed by as a delay item.

(gcd 206 40)
(gcd 40 (remainder 206 40))
->
(if (= (remainder 206 40) 0)
  40
  (gcd (remainder 206 40)
    (remainder 40 (remainder 206 40))))
->
(if (= (remainder 40 (remainder 206 40)) 0)
  (remainder 206 40)
  (gcd
    (remainder
      40
      (remainder 206 40))
    (remainder
      (remainder 206 40)
      (remainder
        40
        (remainder 206 40)))))
...
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP 1.2.3 »

Hide Comments

comments powered by Disqus
SICP 1.2.3 - kamelzcs's library

SICP 1.2.3

Posted on 2015-02-12 20:42:17 +0900 in SICP Lisp

Time and space complexity is kind of difficult for me.

1.14

 (define (count-change amount) 
   (cc amount 5)) 
 (define (cc amount kinds-of-coins) 
   (cond ((= amount 0) 1) 
         ((or (< amount 0) (= kinds-of-coins 0)) 0) 
         (else (+ (cc amount 
                      (- kinds-of-coins 1)) 
                  (cc (- amount 
                         (first-denomination kinds-of-coins)) 
                      kinds-of-coins))))) 
 (define (first-denomination kinds-of-coins) 
   (cond ((= kinds-of-coins 1) 50) 
         ((= kinds-of-coins 2) 25) 
         ((= kinds-of-coins 3) 10) 
         ((= kinds-of-coins 4) 5) 
         ((= kinds-of-coins 5) 1)))

To analyze the time complexity of $cc(n, k)$, it is more easy to start from $k=1$

if $k=1$, then $cc(n, 1)=O(n)$

if $k=2$, then $cc(n, 2) = cc(n - 5, 2) + cc(n, 1) = O(n^2)$

…

By induction, $cc(n, 5)=O(n^5)$

1.15

Time complexity is about $log_3(n)$.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP 1.2.2 »

Hide Comments

comments powered by Disqus
SICP 1.2.2 - kamelzcs's library

SICP 1.2.2

Posted on 2015-02-12 19:25:25 +0900 in SICP Lisp

1.11

Recursive versoin:

#lang planet neil/sicp
(define (f-triple n)
  (cond ((< n 3) n)
        (else
          (+ (f-triple (- n 1))
           (f-triple (- n 2))
           (f-triple (- n 3))))))

Iterate version:

(define (f-triple-iter n)
  (if (< n 3)
    n
    (f-iter 2 1 0 (- n 2))))
(define (f-iter a b c count)
  (if (= count 0)
    a
    (f-iter (+ a (* 2 b) (* 3 c))
            a
            b
            (- count 1))))

1.12

(define (triangle row col)
  (cond ((= col 1) 1)
        ((> col row) 0)
        (else
            (+ (triangle (- row 1) (- col 1))
               (triangle (- row 1) col)))))
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP 1.2.1 »

Hide Comments

comments powered by Disqus
SICP 1.2.1 - kamelzcs's library

SICP 1.2.1

Posted on 2015-02-12 07:59:53 +0900 in SICP Lisp

1.9

(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))

The first version is recursive and the second one is iterative. For the compilers such as Lisp, which implemented tail call optimiztion, they make no difference. But for other compilers such as C, Python, it would make big difference on memory usage and speed.

1.10

(A 0 n) = 2n
(A 1 n) = (A 0 (A 1 (- n 1))) = 2 * (A 1 (- n 1)) = 2 ^ n
(A 2 n) = (A 1 (A 2 (- n 1))) = 2 ^ (A 2 (- n 1)) = 2 ^ (2 ^ n)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP section 1.1 »

Hide Comments

comments powered by Disqus
SICP section 1.1 - kamelzcs's library

SICP section 1.1

Posted on 2015-02-12 04:51:53 +0900 in SICP Lisp

1.3

In order to find out the bigger ones, compare them pairwisely.

#lang planet neil/sicp

(define (square x)
  (* x x))

(define (sum-of-squares x y)
    (+ (square x)
       (square y)))

(define (bigger x y)
  (if (> x y) x y))

(define (smaller  x y)
  (if (< x y) x y))

(define (bigger-sum-of-square x y z)
  (sum-of-squares (bigger x y)
                 (bigger (smaller x y)
                         z)))

1.4

This is the first order useage of the function, which is +

#lang planet neil/sicp

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

1.5

#lang planet neil/sicp

(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))

If it is evaluated in applicative order, then the evaluation of the (p) would lead to infinite loop. While, if it is evaluated in normal order, then 0 would return before it is evaluated.

1.6

(if ⟨ predicate ⟩ ⟨ consequent ⟩ ⟨ alternative ⟩)

If is special form becuase it is not a regular expression, which will have its arguments being evaluted at first.

Onlyconsequent OR alternative will be evaluted, but never both at the same time.

The new-if statement will lead to infinite loop.

1.7

For small numbers, such as (sqrt 0.00000000000002), the accuracy itself is too inaccurate.

For large numbers, such as (sqrt 20000000000000) will be trapped in infinite loop. The guess would be a fixed point which equals 4472135.954995. But 20000000000000/4472135.954995 =4472135.955 which is not equal to 4472135.954995 exactly.

The reason is for float number, when the exp bits gets larger, its coificent bits would loose some accuracy. Accurary lost meet with big exponent number, then this float number becomes inaccurate.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 说好的2014 »

Hide Comments

comments powered by Disqus
posts

Latest

2015-03-16 sicp-4-3-3 Lisp
2015-03-15 sicp-4-3-2 Lisp
2015-03-13 sicp-4-3-1 Lisp
2015-03-12 sicp-4-2-3 Lisp
2015-03-11 sicp-4-2-1 Lisp

Technique

Python variable scope - kamelzcs's library

Python variable scope

Posted on 2013-11-13 00:07:37 +0900 in Technique Python Variable scope

About variable scope

In python, the variable scope has four kinds:

  • global
  • class
  • instance
  • local

In those kinds, the class-based and instance-based may merge in some cases:

Every time, the instance-based is looked up, which has not been initialized, the class-based result will be returned if there is any. Once it is initialized, it will be in the field of the instance.

One example from stackoverflow:

class MyClass(object):
    my_var = 10

    def __init__(self):
        print(self.my_var)


m1 = MyClass()
>>> 10          # class-based 

MyClass.my_var = 20
print(m1.my_var)
>>> 20          # Only class-based available.

m2 = MyClass()
>>> 20          # class-based

m1.my_var = 30
print(MyClass.my_var)
>>> 20          # class-based,but the instance-based variable has been set in m1.

MyClass.my_var = 40 
print(m1.my_var)
>>> 30           
                 # The value WAS shared before m1.my_var = 30 had happened.

print(m2.my_var)
>>> 40           # m2.my_var's value is still shared
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Modeling-Relationship-in-App-Engine »

Hide Comments

comments powered by Disqus
Modeling-Relationship-in-App-Engine - kamelzcs's library

Modeling-Relationship-in-App-Engine

Posted on 2013-11-11 21:15:27 +0900 in Technique Database App Engine

The origin article is in relationship.

The nature of relationships

There are many relationships, such as one to one, one to many and many to many. But the they are all built on the similar idea: reference. A reference is a field of an entity that contains the key of another entity.

Relationships in App Engine

One to many

In app engine, it is accomplished by storing the key of one side in the entity of many side.

class Owner(db.Model):
  name = db.StringProperty()

class Pet(db.Model):
  name = db.StringProperty()
  owner = db.ReferenceProperty(Owner)
pets = Pet.all().filter('owner =', owner).fetch(100)

To fetch all the pets owned by the owner, the query can be in this way.

pets = Pet.all().filter('owner =', owner).fetch(100)
pets = owner.pet_set.fetch(100)

To change the default name to our own name, code can be in the following way.

class Pet(db.Model):
  name = db.StringProperty()
  owner = db.ReferenceProperty(Owner, collection_name='pets')

pets = owner.pets.fetch(100)

Another way to model the one to many relationships is to use parent entities. Every entity can specify a parent when it is created. The key of the parent forms part of the key of the created entity, and cannot be modified. The code is like the following:

class Owner(db.Model):
  name = db.StringProperty()

class Pet(db.Model):
  name = db.StringProperty()

bob = Owner(name='Bob')
felix = Pet(name='Felix', parent=bob)

owner_of_felix = felix.parent

The relationship is specified implicitly. It is the most import case for transactions: on app engine, transactions can only be operate on the same entity group. A entity group is the set with same parent.

One to one

A special case of one to many.

Many to many

The most obvious approach is the same as used in relationship databases: a join table.

class Owner(db.Model):
  name = db.StringProperty()

class Pet(db.Model):
  name = db.StringProperty()

class PetOwner(db.Model):
  pet = db.ReferenceProperty(Pet, collection_name='owners')
  owner = db.ReferenceProperty(Owner, collection_name='pets')

Using the referenceproperty, the code is like the following:

petowners = felix.owners.fetch(100)
prefetch_refprops(owners, 'owner')
owners = [x.owner for x in petowners]

Another approach is to have one side of the relationship store a list of the keys of entities on the other side of the relationship. This makes sense when the cardinality on one side is limited.

class Pet(db.Model):
  name = db.StringProperty()

class Owner(db.Model):
  name = db.StringProperty()
  pets = db.ListProperty(db.Key)

pets = db.get(bob.pets)
owners = Owner.all().filter('pets =', felix).fetch(100)
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Modeling-entity-relationships »

Hide Comments

comments powered by Disqus
Modeling-entity-relationships - kamelzcs's library

Modeling-entity-relationships

Posted on 2013-11-08 04:01:35 +0900 in Technique App Engine Database

One to Many

class Contact(db.Model):

    # Basic info.
    name = db.StringProperty()
    birth_day = db.DateProperty()

    # Address info.
    address = db.PostalAddressProperty()

    # The original phone_number property has been replaced by
    # an implicitly created property called 'phone_numbers'.

    # Company info.
    company_title = db.StringProperty()
    company_name = db.StringProperty()
    company_description = db.StringProperty()
    company_address = db.PostalAddressProperty()

class PhoneNumber(db.Model):
    contact = db.ReferenceProperty(Contact,
                                   collection_name='phone_numbers')
    phone_type = db.StringProperty(
        choices=('home', 'work', 'fax', 'mobile', 'other'))
    number = db.PhoneNumberProperty()

Everytime a reference property is created, an implicit collection property on the referenced class is created. The default name can be over-rode using collection_name.

Now the relationship can be created in the following way.

scott = Contact(name='Scott')
scott.put()
PhoneNumber(contact=scott,
            phone_type='home',
            number='(650) 555 - 2200').put()
PhoneNumber(contact=scott,
            phone_type='mobile',
            number='(650) 555 - 2201').put()

Now the phone numbers for a give person can be retrieved in this way.

print 'Content-Type: text/html'
print
for phone in scott.phone_numbers:
    print '%s: %s' % (phone.phone_type, phone.number)

Many to many

class Group(db.Model):

  name = db.StringProperty()
  description = db.TextProperty()

class Contact(db.Model):
  # ID of user that owns this entry.
  owner = db.StringProperty()

  # Basic info.
  name = db.StringProperty()
  birth_day = db.DateProperty()

  # Address info.
  address = db.PostalAddressProperty()

  # Company info.
  company_title = db.StringProperty()
  company_name = db.StringProperty()
  company_description = db.StringProperty()
  company_address = db.PostalAddressProperty()

  # Group affiliation
  groups = db.ListProperty(db.Key)

friends = Group.gql("WHERE name = 'friends'").get()
mary = Contact.gql("WHERE name = 'Mary'").get()

if friends.key() not in mary.groups:
   mary.groups.append(friends.key())
   mary.put()

class Group(db.Model):
   name = db.StringProperty()
   description = db.TextProperty()

   @property
   def members(self):
      return Contact.gql("WHERE groups = :1", self.key())

The limitations:

  1. Must explicitly retrieve the values on the side of the collection where the list is stored since all you have available are Key objects
  2. Avoid storing overly large lists of keys in a ListProperty

Relationship Model

class Contact(db.Model):
    # ID of user that owns this entry.
    owner = db.StringProperty()

    # Basic info.
    name = db.StringProperty()
    birth_day = db.DateProperty()

    # Address info.
    address = db.PostalAddressProperty()

    # The original organization properties have been replaced by
    # an implicitly created property called 'companies'. 

    # Group affiliation
    groups = db.ListProperty(db.Key)

class Company(db.Model):
    name = db.StringProperty()
    description = db.StringProperty()
    company_address = db.PostalAddressProperty()

class ContactCompany(db.Model):
    contact = db.ReferenceProperty(Contact,
                                   required=True,
                                   collection_name='companies')
    company = db.ReferenceProperty(Company,
                                   required=True,
                                   collection_name='contacts')
    title = db.StringProperty()

mary = Contact.gql("name = 'Mary'").get()
google = Company.gql("name = 'Google'").get()
ContactCompany(contact=mary,
               company=google,
               title='Engineer').put()

The advantage compared with list-of-keys is can have large collections on either side of the relationship. However, the traversing the connectionso of a collection will require more calls to teh databases.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Transaction Isolation in App Engine »

Hide Comments

comments powered by Disqus
Jinja2 - kamelzcs's library

Jinja2

Posted on 2013-10-29 21:56:46 +0900 in Technique Jinja2 Template

Variables

{{ foo.bar }}

{{ foo[‘bar’] }}

Implementation

Sake foo.bar in Jinja2 does the following thing on the Python layer:

  • check if there is an attribute called bar on foo.
  • if there is not, check if there is an item ‘bar’ in foo.
  • if there is not, return an undefined object.

foo[‘bar’] works mostly the same with a difference in the order:

  • check if there is an item ‘bar’ in foo.
  • if there is not, check if there is an attribute called bar on foo.
  • if there is not, return an undefined object.

###Filers### Variables can be modified by filters.
{{ name|striptags|title }} will remove all HTML Tags from the name and title-cases it.

###Tests### Tests can be used to test a variable against a common expression.

{% if loop.index is divisibleby 3 %}

###Comments###

{# note: disabled template because we no longer use this
{% for user in users %}
…
{% endfor %}
#}

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Git Commands »

Hide Comments

comments powered by Disqus
Git Commands - kamelzcs's library

Git Commands

Posted on 2013-10-29 20:31:03 +0900 in Technique Git

Here is a useful tutorial for Git:Visual git guide

  • git status

    Check the status of the files.

  • gitk -all & git diff

    show the branch in graphical mode.

    check the difference.

  • git rm

    remove files

  • git log

    • git log -p -2

      show the changing between the past two submitions

    • git log --oneline

      Condense each commit to a single line.

    • git log --stat

      Along with the ordinary git log information, include which files were altered and the relative number of lines that were added or deleted from each of them.

  • git commit --amend

    replace the last submit

  • git reset HEAD

    unstage files

  • git add .

    add all the files in the subdirectory.

  • git checkout \<file\>-

    unmodifying a modified file, revert it back to what it looked like when last committed.

  • git remote -v

    shows the URL for the shorname to be expaned to

  • git remote show origin

    list the more infomation of the remote

  • git push origin local-branch-name:remote-branch-name

    push to specilized banch

  • git push origin :newfeature

    delete remote branch newfeature

  • git merge --squash bugfix&git commit -m 'fix bug'

    Take all the commits from the bugfix branch, squash them into 1 commit and then merge it with the master branch

  • git fetch origin & git checkout -b test origin/test

    fetch all the remote branches and checkout the specific branch

  • git branch -a

    show the branch info in remote and local

  • git checkout --track

    set the track branch

  • git rebase

    take all the changes that were commited on one branch and replay on another one.

    • git rebase -i \<the SHA-1 of unchanged commit\>

      merge multiple commits pick = use the commit squash = use commit, but merge into previous commit

  • git cherrypick <the SHA-1 of unchanged commit>

    pick the specified commit to the current branch

  • git diff \<branch\> \<branch\>

    compare the difference between two branches

  • git stash save 'comment'

    save the changes temporary

    • git stash list

      view the stash list

    • git stash apply stash@{2}

      apply the specified stash.

    • git stash apply --index

      reapply the staged changes

    • git stash drop

      remote from the stash list

    • git stash pop

      apply the stash and immediately drop it from the stack. Be causious.

    • git stash branch

      creating a branch from a stash

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 日本大使馆活动见闻 »

Hide Comments

comments powered by Disqus
posts

Latest

2013-11-13 Python variable scope Python Variable scope
2013-11-11 Modeling-Relationship-in-App-Engine Database App Engine
2013-11-08 Modeling-entity-relationships App Engine Database
2013-10-29 Jinja2 Jinja2 Template
2013-10-29 Git Commands Git

Technology

Understanding Git - kamelzcs's library

Understanding Git

Posted on 2013-12-28 04:20:24 +0900 in Technology Git

What is in Git is snapshots

The most obvious feature in Git owns all the snapshots of the system, while most other VCS system only stores the differences.

alt normal

Figure 1-1. VCS usually only stores the differences.

alt normal

Figure 1-2. Git stores the snapshots.

In order to get data efficienty, the Git compresses each ‘original’ file and calculate its SHA-1
hash, then use a tree structure to store the whole infomition hierarchically.

The three states in Git

In Git, there are three states: the working directory, staging area and Git directory.

alt normal

Figure 1-3. Git states

The basic working flows is as follows:

  • Making changes in working directory.

  • Stage the useful changes and add their snapshots to the staging area.

  • Commit the staging area to the Git directory, which will store the snapshots of the staging area permunantly.

How the Git store the snapshots

The Git tree object

The Git store thing similar to the Unix system: the tree object corresponds to the directory entity while the blog corresponds to the inode or file.

alt normal

Figure 1-4. Tree object

alt normal

Figure 1-5. Content structure of the tree object.

alt normal

Figure 1-6. Single commit in a compatible way.

The Git directory

The Git tree structure is as follows:

alt normal

Figure 1-7. Git directory

alt normal

Figure 1-8. Git directory in a compatible way.

The Git branch

The Git branch is a pointer to a commit, the HEAD is the pointer to your current branch.

alt normal

Figure 1-9. Git branch

alt normal

Figure 1-10. Git head.

Reference

[1] Visual git tutorial

[2] Git tutorial

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Vim Tips »

Hide Comments

comments powered by Disqus
Vim Tips - kamelzcs's library

Vim Tips

Posted on 2013-12-06 20:08:11 +0900 in Technology Vim

Here is some useful Vim tips

Normal

  • V multiline copy

  • . duplicate last command

  • I insert at the begin

  • A Append to end

  • J Join two lines

  • > and < indent block(in visual mode)

  • CTRL + A or X increase or decrease the number

  • ~ toggle the casing of a letter/selection(upper-case/down-case)

  • !! execute last command

  • <start position><command><end position> for example y`a yank from here to he marked a

  • use markers in the way a z b e

  • "zyy and "zp copy to z register and paste from z register

  • set ft=? look up current file type.

Move

  • % go to the corresponding (),{},[]

  • mz `z Marker and go to the last position

  • '. Jump back to last edited line

  • g;and g, move (forward,backward) through the changelist

  • gi go to the last place you inserted a text

  • Ctrl-o and Ctrl-i to go to the previous/next location you jumped to

  • fa go to the next a in the line

  • t, go to before the next ,

  • F and T are backward

  • w go to the start of the next word

  • b/e go to the beginning/end of this word

  • W go to the start of the following WORD(space separated only)

  • B/E go to the beginning/end of this WORD

  • { } to move to the beginning/ending of the paragraph

  • zz move current line to the middle of the screen

  • zt move current line to the top of the screen

  • zt move current line to the bottom of the screen

  • Ctrl+e move screen up one line

  • Ctrl+y move screen down one line

Zone selection

<action>a<object> and <action>i<object>

Action can be any action, for example d, y, c(change), v(select in visual mode). The object can be: w a word, W a WORD, s a sentence, p a paragraph. But also, natural character such as ",',),],}

vi" will select foo.

va" will select “foo”

Editing

  • cc change the entire current line

  • r replace the current character

  • R Enter Insert mode, replacing characters rather than inserting

Macro recording

/bin/bash: :q: command not found

  • q[ key ] to start recording

  • q to stop recording

  • @[ key ] to use the macro ```

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 左宗棠题江苏无锡梅园 »

Hide Comments

comments powered by Disqus
Transaction Isolation in App Engine - kamelzcs's library

Transaction Isolation in App Engine

Posted on 2013-11-07 03:26:26 +0900 in Technology App Engine Database

Inside Transactions: Serializable

From strongest to weakest the four isolation levels are Serializable, Repeatable Read, Read Committed, and Read Uncommitted. Transactions are separated within each other. Transactions on a given entity group are executed serially.

Within the transaction, the datastore is consistent.

The Commit Process

The process is as below:

alt normal

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Life of a Datastore Write »

Hide Comments

comments powered by Disqus
Life of a Datastore Write - kamelzcs's library

Life of a Datastore Write

Posted on 2013-11-07 03:02:45 +0900 in Technology App Engine Database

An Insert

When we call put or makePersistent, several things happen behind the scenes before the call returns and sets the entity’s key:

  1. The my_todo object is converted into a protocol buffer.
  2. The appserver makes an RPC call to the datastore server, sending the entity data in a protocol buffer.
  3. If a key name is not provided, a unique ID is determined for this entity’s key. The entity key is composed of app ID ancestor keys kind name key name or ID
  4. The datastore server processes the request in two phases that are executed in order: commit, then apply. In each phase, the datastore server identifies the Bigtable tablet servers that should receive the data.

The Commit Phase

The datastore performs two actions in the commit phase:

  1. It writes the data for the entities to the entity group’s log.
  2. It marks the new log entry as committed.

The Apply Phase

In the apply phase, the entity’s data and the index rows are written to disk in parallel.

The Return Value

Using HRD, the Datastore returns after the commit and does the apply asynchronously.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Storing Data in App Engine »

Hide Comments

comments powered by Disqus
posts

Latest

2013-12-28 Understanding Git Git
2013-12-06 Vim Tips Vim
2013-11-07 Transaction Isolation in App Engine App Engine Database
2013-11-07 Life of a Datastore Write App Engine Database

Vim

Install solarized color theme - kamelzcs's library

Install solarized color theme

Posted on 2013-11-19 20:32:13 +0900 in Vim Vim Solarized

It is not so easy to correct configure the solarized for vim and gnome. It should be done in several steps.

Install gnome solarized color theme

Use Bundle to install the gnome, after this, the background is ok, but the ls command only displays grey. It should be fixed.

Fix the ls command

Use this fix.

Install vim solarized color theme

Use Bundle to install vim solarized.

color test

scipt5

scipt6

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Python variable scope »

Hide Comments

comments powered by Disqus
posts

Latest

2013-11-19 Install solarized color theme Vim Solarized

jekyll

如何使用模板 - kamelzcs's library

如何使用模板

Posted on 2012-12-28 06:44:30 +0900 in jekyll Jekyll Git Github

1 介绍

在github上搭建一个中小型网站，可以充分利用github提供的托管功能，并且不用担心代码丢失的问题，是一件很惬意的事情。

2 安装

基本参照http://kamelzcs.github.com/2012/08/14/blogging-with-jekyll/即可。 说明几个需要注意的问题：

  1. 建立 username.github.com 这样的repo，这样就可以直接使用这个域名访问网站.
  2. _compiled主要用来中转,将_site拷贝过来之后，然后将目录切换到 _compiled，因为 _compiled 克隆的时候用的是master，所以自动切换到了master分支，然后提交到master分支。这里有个疑问,_compiled既然克隆出来的时候是在master分支，为什么在source分支下又可以看到这个文件夹，暂时不清楚。
  3. git会自动确定切换分支时哪些文件该出现，哪些不应该出现。

2013年10月28日 更新： jekyll升级到1.2.1 以后，jekyll-pagination会导致jekyll在 build的时候失败，只能将pagination.rb手动更新为最新的代码,同时__plugin文件夹中不能使用中文。

2015年1月21日 更新： jekyll升级到2.5.4 以后，jekyll-pagination已经被内置jekyll-paginate代替。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
« 

Hide Comments

comments powered by Disqus
posts

Latest

2012-12-28 如何使用模板 Jekyll Git Github

life

Goals in 2014 - kamelzcs's library

Goals in 2014

Posted on 2014-02-03 01:01:43 +0900 in life life

About Japanese Learning

I would like to take the J3 level example in the December of 2014. J3 requires at least master three books, that is, Primary 1, Primary 2 and Middle 1. Now I have Learned half of them. But besides learning, it is very important to take exercises as well, which I still did not pay enough attention on.

There are 25 lessions within one book, it usually takes at least two days to learn one lesson. So it takes two months to learn book, so at the beginning of May I should finish the learning of them and begin to do exercises.

Weekly Goal: three lessons and one attendance of Japanese language Learning.

Yearly Goal: Pass J3 and make a presentation in the Official building.

About Data Analysis

Now in the working, it is very important to analyze the data of the website, escecially there is no data analysis in the group now.

Within this year, there will be about 9 opening class in the Coursera which being given by John Houpkins University.

Weekly Goal: Follow the course in the coursera and finish the exercises as well.

Yearly Goal: Master R and be able to analyze the data in the Google analysis using R.

About Programming

Within this year, a totally new Labola web system will be built. In this way, I should know everythin the full stack developer should know. Due to lack of knowledge in the web development, it should be a tough task for me at first, but everything would go well after this year.

From selecting system framework to develop the system and test, publish. I should take the role and make preparation to be a leader of the develop team.

In order to improve the programming skill, I should participate in the open souce project as well.

weekly Goal: write one blog about the open source project.

Yearly Goal:

2014.2 to 2014.6: read one python open source project and one C++ open source project.

2014.6 to 2014.12 Participate in one open source project.

About interest

About soccer: try to play three times a week and try to be a important part of the team, to be a player in the real match, not only in the friendship match.

About Learning meeting: try to particitae one learning meeting within one month and try to ask for questions when particitate.

About social network: use Facebook, weibo, Linked in, tweet more. Make a new post every week about the technology and about the life each.

About weight: 70KG is the finally goal, reach 72 KG before 2014.6.

At last

Summarize the goals listed weekly, monthly and report.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Linklist Mergesort »

Hide Comments

comments powered by Disqus
posts

Latest

2014-02-03 Goals in 2014 life

technique

Storing Data in App Engine - kamelzcs's library

Storing Data in App Engine

Posted on 2013-11-05 23:59:29 +0900 in technique Database App Engine

Storing Data

The app engine provides several ways to store data for the application:

  1. App Engine Datastore: A schemaless object datastore with automatic caching, query engine, and atomic transactions.
  2. Google Cloud SQL: A relationship SQL based on the MySQL database.
  3. Google Cloud Storage: size can be up to terabytes.

Python Datastore API

An entity has one or more properties. Each entity is identified by its kind, which categorizes the entity for the purpose of queries, and a key that uniquely identifies it within its kind.

import datetime
from google.appengine.ext import db
from google.appengine.api import users


class Employee(db.Model):
  name = db.StringProperty(required=True)
  role = db.StringProperty(required=True,
                           choices=set(["executive", "manager", "producer"]))
  hire_date = db.DateProperty()
  new_hire_training_completed = db.BooleanProperty(indexed=False)
  email = db.StringProperty()


e = Employee(name="John",
             role="manager",
             email=users.get_current_user().email())
e.hire_date = datetime.datetime.now().date()
e.put()

Query Examples:

training_registration_list = ["Alfred.Smith@example.com",
                              "jharrison@example.com",
                              "budnelson@example.com"]
employees_trained = db.GqlQuery("SELECT * FROM Employee WHERE email IN :1",
                                training_registration_list)
for e in employees_trained:
  e.new_hire_training_completed = True
  db.put(e)

Comparison with traditional databases

It differs from them in the way it describes relationships between data objects. Entities of the same kind can have different properties, and different entities can have properties with the same name but different value types.

Entities

Objects in the Datastore are entities.

Kinds,keys, and identifiers

Each entity is a particular kinds, which categorizes the entity for the purpose of queries. In addition, each entity has its own key, which uniquely identifies it. The key consists of the following components:

  1. The entity’s kind
  2. identifier, which can be either
    • a key name string
    • an integer ID
  3. An optional ancestor path locating the entity within the Datastore hierarchy

Ancestor paths

Entities in the Datastore form a hierarchically structured space similar to the directory structure of a file system.

[Person:GreatGrandpa, Person:Grandpa, Person:Dad, Person:Me]

Queries and indexes

A typical query includes the following:

  • An entity kind to which the query applies
  • Zero or more filters based on the entities’ property values, keys, and ancestors
  • Zero or more sort orders to sequence the results

App Engine predefines a simple index on each property of an entity. An App Engine application can define further custom indexes in an index configuration file named index.yaml.

Transactions

Every attempt to insert, update, or delete an entity takes place in the context of a transaction. A single transaction can include any number of such operations. To maintain the consistency of the data, the transaction ensures that all of the operations it contains are applied to the Datastore as a unit or, if any of the operations fails, that none of them are applied.

You can perform multiple actions on an entity within a single transaction.

Transactions and entity groups

Only ancestor queries are allowed within a transaction: that is, each transactional query must be limited to a single entity group. The transaction itself can apply to multiple entities, which can belong either to a single entity group or (in the case of a cross-group transaction) to as many as five different entity groups.

Cross-group transactions

The transaction can be applied across a maximum of five entity groups, and will succeed as long as no concurrent transaction touches any of the entity groups to which it applies.

As in a single-group transaction, you cannot perform a non-ancestor query in an XG transaction. You can, however, perform ancestor queries on separate entity groups.

Datastore writes and data visibility

Data is written to the Datastore in two phases:

  1. In the Commit phase, the entity data is recorded in a log.
  2. The Apply phase consists of two actions performed in parallel:
    • The entity data is written.
    • The index rows for the entity are written. (Note that this can take longer than writing the data itself.)

The write operation returns immediately after the Commit phase and the Apply phase then takes place asynchronously.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Jinja2 »

Hide Comments

comments powered by Disqus
posts

Latest

2013-11-05 Storing Data in App Engine Database App Engine

生活

初体验 - kamelzcs's library

初体验

Posted on 2013-03-12 23:50:50 +0900 in 生活 生活

1 帝都的工作

从马斯洛需求模型来讲，人类工作的目的也大抵分为这三类：第一类为生活所困，工作无非就是生存下去的手段，第二类为大抵能做着自己喜欢的事情，工作也大抵能够满足自己不太过分的要求，有时候明明自己很不喜欢做的事情，往往也因为生活所迫不得不就范，第三类大抵就是能够在工作上得心应手，且物质精神上都十分满足的人了。

在每个社会当中这三者的比例是不同的，但是绝对和时间和地理因素有关，作为个人来讲，这绝对和社会有莫大的关系，一人之力是基本不能阻挡社会的洪流的，北京早上的地铁就是最好的证明：无论一个人是多么的君子，只要他不得不在高峰期的地铁上，那么他所有的修养和尊严都不得不放下，生存，是唯一的法则。

在当前的国内社会状况下，这是一个投机远比实干有价值的时代。在这个地方，同事间业余生活的主题基本就是房子、房子、房子。年轻人天天盼着自己老家的旧房子和地能在旧城改造中被拆迁到，然后就能大发一笔，要不就是讨论国家宏观调控的政策，不断的学习国家的政策文件，以期能够像90，00年代抓住房地产改革的红利，或者是2000年前互联网高速扩张，像马云、丁磊等一夜爆发的奇迹，但是，时代不同了，留给我们的现实世界是：利益分配的规则已经画好了，我们局外人很难改变这种利益分配严重不均的格局，于是乎，想法设法的利用制度成为每个人最大的兴趣和努力的方向。在北京，人口2600万（无官方数据），汽车512万辆，房价均价3W+，空气质量全国基本最差，但是它仍然是多数人的首选。

首先，北京有无与伦比的资源。这包括最优质的教育资源，这是留给后代最有价值的财富，也有最优质的医疗、交通、精神生活。一句话，全国最优质的资源+全国最优秀的人才打造了一个让人梦寐以求的北京。其次，因为北京有很多地方没有的机会，比如说互联网公司，除了北京，其他地方发展差距太大，由于地域问题所导致的发展不均，然后又因为发展不均导致了诸如户口制度、地域歧视等等问题，马太效应会加剧这种现象，对人次的吸引能力严重不均从长远来看，诸如此类现象也将会越来越严重。

大多数人都是制度的牺牲品，在发展速度渐渐变缓的社会大环境面前，年轻人成功的机会相对少的多，制度的制定者已经将年轻人向上的空间挤兑的很小，大多数人只能成为所谓中国梦的打工者，当贡献完自己的青春之后，被北京淘汰，然后下一批的年轻人怀揣着梦想到来，周而复始。

这样的社会现实面前，人不为钱工作是不可能的。当背负着沉重的房贷与家庭的不菲开销时，就像在地铁上一样，所做的只有顺从。在这里绝大多数人都是为钱工作，自己凭什么能够不被这个城市淘汰呢？

做自己喜欢的、有价值的事情，能够不为钱工作是我的目标。

2 公司文化感触

作为一个有上万员工的公司，内部势必存在着内耗与斗争。组织机构庞大，行动就变得迟缓。沟通的成本特别高，对资源的争夺也特别的激烈。于是乎，每天都要开几个会，如果部门涉及到比较多的业务逻辑，需要跟多个部门交流，整个过程十分的繁琐。绝大多数的会议主角就是领导与汇报者，因为其他的成员很难知道汇报者业务的具体情况，所以，基本上会议的90%以上会一无所知，另外的10%或许能知其一二。 很讽刺的情况在于，很多时候重复造轮子居然会比通过流程申请某些资源来的快的多。 非休假状态下，基本上工作就等于生活，无法想象晚上十点之前到家是个什么情形，其实，对自己充电才是最终要的。

3 做一个主动的人

并不是永远都只有悲观的消息，有的进入公司的时候就带着某种光环，基本上注定会成为明日之星，大多数人都是从默默无闻，自己慢慢做起来。今天刚刚上线了一个新的功能，次功能对与公司来说不能算是大工程，但是绝对很有意义。一个前辈从发现这个问题，然后利用自己原有的一些积累，最后联合了非常多的部门以及外部的资源，最终能够将这个事情定下来，并且终于能够今日上线。最为一个牵头人，他的主动性让我感到十分的佩服。

4 技术还是管理

高层的技术不是很清楚，能做到top固然NB，但是还是保证做到top之前能保证基本的身体健康吧，颈椎病和腰肌劳损屡见不鲜。眼看着自己的肚子越来越大，却苦于帝都的空气不敢造次，这是一个什么样的恶性循环。每次看着老大中午躲在休息室吃泡面，我都觉得很异样，管理者要开会，开会开会…爬不到上面日子就好过不得，或许这也是大家加班的原因吧

5 跳跃式发展

我们听到过顺丰的快递员收入上万，或者说早晨卖煎蛋饼的商贩如此赚钱的说法。但是都忽略了一个说法，这种收入的增长是线性的，因为只会随着自己的熟练程度增加，然后趋于稳定。线性增长的工作很难收入上有大的breakthrough，个人成长也是一样的，什么样的事情能够让自己跳跃式发展而不是线性发展才是最终要的。

6 财富自由

我来到这个世界上就想多看看，像这对老夫妻一样,达到这一点财富自由是必须的，我想展现自己的价值，能够多为他人带来一些帮助。实现财富自由是一条漫长的学习之路，但是，生活不是目的，生活的终点都是一样的，但是过程就不一样了，米什么的都是浮云，能够多漂一漂才是最幸福的。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 回乡路上 »

Hide Comments

comments powered by Disqus
回乡路上 - kamelzcs's library

回乡路上

Posted on 2013-02-13 00:36:41 +0900 in 生活 诗歌

我远远的观望者别人的生活，
自己却仿佛没有生活过一样。
列车无时无刻不在翻山越岭，
自己却不知道下一站在何方。
那曾经熟悉的面孔依旧，
自己却面目全非。
那曾有的欢歌笑语已经远去，
如今却只能兀自发呆。
出发了太久，
竟模糊了当初梦想的模样。
但是我并不愿意妥协，
我想去远方，
用脚步丈量高山，
用双手拥抱大川。
山川就在那里，
远方也在那里，
出发了不要问路在哪，
一直向前是唯一的方法。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 春节 »

Hide Comments

comments powered by Disqus
春节 - kamelzcs's library

春节

Posted on 2013-02-12 05:02:53 +0900 in 生活 亲情

1 回家

依如往常，今年回家比较晚。由于是一个人，又是早上五点四十到站，也不知道是不是有点兴奋，但是担心睡过站肯定是更主要的原因，下车的第一个感觉还是冷，冰凉刺骨的风吹的让我站不住，在县城等车的时候，原来小的时候觉得车特别多，路特别宽的一条路，现在觉得其实和学校里面的公路差不多，县城来了很多很多次了，但是每次来都是到想到的地方，一般是买件衣服或者别的东西，然后就回家，家里的县城应该是在我心中最大的一个地方，因为从小到现在我都不知道它到底有多大，所以我就一直觉得它很大很大，现在我仍然这么觉得。

在姥姥家呆了大半天之后，下午早早的就走路回家了，原来读初中的觉得特别的远，没想到其实走回去也就半个小时左右，其实和从学校走到寝室差不多。路没有变，我的脚步变长了，走的路和见的事情也多了，那曾经觉得特别有挑战性的事情、特别宽和远的路也变得平常起来。

2 年夜

晚上八点春晚开始，爸爸妈妈准时守在电视前看春晚，我则开着电脑，边看春晚，边在网上玩。其实心里还是有些期待的，每年都期待着当年的春晚能够让我喜出望外，但是基本上每年都很失望，就像中国男足一样，只是每次都很失望。未来总是被期待着，只是往往我的期待不合时宜的高，也许是太乐观，生活总是会不时的给我惊醒，告诉我要以一颗平常心看待成成败败。刘谦和郭德纲是我比较期待的，只是一个给我的感觉是表演没有达到我的预期，一个的幽默方式自己无法感同身受。

十二点我并没有像往年一样点燃爆竹，现在觉得爆竹很危险还没有太大的意思，还远远没有爸爸对爆竹感兴趣。村子里鞭炮声已经远远不能与当年相比，现在村子里面的年轻人很少了，村里的年轻人都搬到县城或者镇上了，只剩下了中老年人留守。

3 拜年

血缘关系中五服的计算方法：由于古代一夫多妻，因此，同父又同母的是一服，即所谓“同胞”、“一奶同胞”；同父不同母的是二服，例如《红楼梦》中贾宝玉与贾环。同祖父的是三服，例如《红楼梦》中贾宝玉与贾琏，同曾祖父的是四服，例如《红楼梦》中贾宝玉与宁国府的贾珍；同高祖父的是五服。 现代实行一夫一妻制，除非父亲离婚、丧偶后再婚再生育，一二服之间的区别通常消失，因此计算起来会令人困惑，错以为五服就是五代，实际上五服只四代。从祖父开始向上，不再分别妻妾的子女。

早上五点半爸爸妈妈就起床了，新年的饺子是必不可少的，我起来后先给家里的亲戚朋友打电话拜个早年，在农村住的都打通了，城市里面的基本都没有打通，后面见了面才知道在城市的基本没有拜年，所以就没有早起。

八点半出门，去奶奶家，这是集合的开始。一直等到十点钟左右，在城市住的哥哥们带着一家人赶到奶奶家，我们就浩浩荡荡的出门了。拜年的队伍由我们五服之内的小辈向长辈问好，由于爷爷自己是兄弟四个，仅仅我爷爷就有五个儿子，所以拜年的队伍有20多个人。拜年到长辈家里，然后简单的聊一聊，主要是认一认亲，日后见着打招呼辈份不会出错。

4 年聚

中午我们整个家族的人到了城里已经预订好的酒店，今年是二爷组织招待的，整个安排的非常好。做了两桌，一桌上坐的是我的爸爸的辈份的，另外一桌坐的是我们这些小辈的。其实现在小辈的也平均有将近30岁了，哥哥姐姐们基本上都在市工作生活，事业上也算是小有所成，有的可能几年才能见一次。大家坐在一起现在基本都是讨论孩子、房子的问题，他们属于房子买的比较早的，像我这种现在还没有着落的，听着这些个问题就觉得听麻烦的，虽然觉得离自己还是比较远，但是仔细想想，其实也是很快的事情了，年轻人的梦想往往都是被无情的房价给消磨掉了，有一个哥哥为了孩子能读一个好的高中，贷款买学区房，各种压力，让我觉得蛮无奈的。

5 长大

一转眼，就要26了。自己没觉得什么，倒是家里人总是问我婚姻、工作什么的。爷爷奶奶、姥姥姥爷都80+了，他们都在，让我觉得和小的时候差不多。爸爸妈妈待我仍如当初念初中高中那般，这种感觉蛮幸福的。喜欢一家人在一起热闹的感觉，在一起像当初一样嘻嘻笑笑的感觉，只是，现在大年初二要和表姐们的孩子们玩了，姐姐们都当了妈妈，终于没有人和我抢遥控器了，只是我也没有时间看电视，要陪客喝酒，还要力所能及的张罗下屋里屋外的事情，忙忙碌碌，却又有时候觉得没有当初好玩了。

长了了，意味着更多的责任，也意味着老一辈人渐渐退出主流的舞台，开始慢慢的退居后台。喜欢爸爸妈妈他们的生活态度，勤劳、吃苦、目标明确，他们真是我的好榜样，虽然生活上打打闹闹，但是他们身上那不服输的精神一直在激励着我。在我看来，父母的言传身教是最好的老师，他们之于我的东西我会珍存一辈子，受用一辈子。

可能这是最后一次如此惬意的寒假，也是我最后一次还能装装孩子，装着没长大，和爸爸没大没小的开着玩笑，多年父子成兄弟，无论有什么事情，虽然我现在文化水平比他们高一些，但是还是会和他们沟通，让他们也知道我的想法，他们也能明白我所说的道理。他们对我一直以来的支持是我一直以来最珍惜的财富。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | review 2012 »

Hide Comments

comments powered by Disqus
review 2012 - kamelzcs's library

review 2012

Posted on 2013-01-02 07:18:59 +0900 in 生活 回忆 展望

1 回首

过去的2012年是失去的一年，是获得的一年，有很多遗憾，但是也有很多新的经历，总的来说，在这相对安稳的一年当中，收获相对往年有所减少，这是值得反思的一件事情。

从3月份返校，开始着重分析、搭建完成第一个机器学习相关的中央高校创新基金，同时，重点分析、优化Ray Tracing中的BVH，在六月份的时候完成了机器学习项目的初版并完成答辩，在六月份获得了优化的一个idea，开始动手写作。写作从动手，到回头做实验，完成初稿，投稿，历时一个月的时间。然后开始着手准备暑假去日本暑期学校的事情。原本以为去日本的暑期学校能勾兑下老师，最终的结果是惨不忍睹，只认识了一位美帝的老师，但是感觉学校不是太满意。从日本回来，也与在美帝读Ph.D的廖老师聊了不少，最终决定还是先找个工作，去美帝读Ph.D的想法基本上放弃了。

回校处理了点杂事，然后就开始准备找工作了。从刚开始百度、腾讯的顺利，到MS、google、Facebook的悲剧，整个过程算是高开低走，这也让我当初过于乐观和准备不足的缺点暴露了出来。代码能力本来就不是我的强项，加之准备又如此不充分，到最后只能是一个高不成，低不就的局面。

妹子找到了一份日本的工作，我和她都觉得工作挺好的，但是这样的话，很有可能要异地了。妹子是个要强的人，同时自己现在也不能够一个人就能把家里撑起来，里外为难。

2 抉择

一个是国内互联网公司的机器学习职位的研发工程师，没有户口，开始的薪资也是一个平均值，未来的发展也不是很确定。这样的好处是自己可以继续做技术，同时，有相对简单的工作环境，晋升与否完全看自己在工作中能力的表现，未来想在互联网公司间跳槽的话也相对简单，同时上升空间应该是没有限制的，限制自己的就是工作能力了。同时，如果两个人异地的话，这份工作能够帮助我去日本的概率要大的多。缺点来说，工作的强度应该会比较大，按照坊间传闻来说，朝九晚十可能是家常便饭，业余生活和健康应该是比较大的牺牲。

另外一个是银行的软开。按照IT技术在银行的地位来说，发展的空间要相对小一些，同时，作为国企，技术能力并不是最重要的，需要的是更好的综合能力。在这个方面，本人从小就没有接触过这种事情，同时，在性格方面，想要在里面要好的发展，必须要改变些东西。这个offer意味着相对稳定的生活，但是较小的上升空间，在生活和健康上有较好的保障，但是想出人头地基本很难了。

还有一种可能就是找到去日本的工作，作为自己来讲，去日本，还是想多多学习更好的前沿技术，这样在面对将来可能的变数时才会有更好的选择的机会，如果仅仅为了选择一个稳定的生活，我认为其意义并不是如此之大，毕竟，可能安逸的生活国内也能有，但是，发展的机会的话，应该没有国内好。毕竟，定居这个问题还是要考虑多种因素的，与日本的种种不缺定的未来，这是一个不得不考虑的问题。

一个选择基本上就意味着将来非常不同的生活轨迹。

3 展望

希望来年自己去北京实习能够结交到新的朋友，能够适应公司的生活，同时能够多方面的了解信息，争取能够有更好的选择，希望也能够有更好的机会，如果去日本工作的话，希望大家都能顺顺利利的，同时，能够更多的了解业内的动向，结交更多的朋友，有更好的身体，能够找到一条双方都能接受的，早日不再异地的途径。未来很美好，但是自己过还是觉得太苦逼，不好玩。作为自己来讲，在我看来，自己的优势应该是一个较为整体的素质。我不是一个标准的Geek，但是，希望自己能够多读书，多接触挑战性的问题，也希望能够有好的运气，相信未来！

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 如何使用模板 »

Hide Comments

comments powered by Disqus
posts

Latest

2013-03-12 初体验 生活
2013-02-13 回乡路上 诗歌
2013-02-12 春节 亲情
2013-01-02 review 2012 回忆 展望

讲座

日本大使馆活动见闻 - kamelzcs's library

日本大使馆活动见闻

Posted on 2013-03-17 08:23:16 +0900 in 讲座 日本 生活

1 所见所闻

本次活动邀请到了NHK Radio《波短情长》的主播人，也是著名的作家，许丹青老师。许老师从87年就开始在日本工作，但是至今还保留着中国国籍。其中的原因，他没有讲，但是他讲过这样一句话：虽然日本文化从中国借鉴了很多东西，但是在日本呆的时间越久，就越会觉得中日两种文化的不同，而不是觉得相近。之所以没有选择归化，应该还是和这种来自内心的文化认同感有关系。

许老师在日本大学任教，同时还在电台担任主持人，他的居住地在长角?，每周都要坐新干线去东京录制节目，他说他最骄傲的一件事情就是这么多年以来，从来没有因为大雨台风之类的原因迟到过。我想这也许就是日本精神内涵之一吧，敬业。

许老师讲到的最让我感动也是最让我震撼的是日本人内心存在对土地、对自然的敬畏之情。他讲了这样一个例子：他有一个学生，暂称为小野，小野来自农村，家里父亲是种茄子的。小野是一个很有上进心的人，打算毕业之后到东京去闯荡一番，并且，也拿到了东京的公司的offer，许老师在毕业之前，请他去一家中国的东北菜餐馆吃饭，也算是践行。许老师点了地三鲜（茄子，土豆，青椒），小野吃了一口茄子，然后突然就有点呆住了，眼睛有点发红的感觉，许老师以为出了什么事情，很担心的问他怎么了，小野缓缓的说道：我从来没有吃过这么好吃的茄子，原来茄子是这么的好吃。我决定了，不去东京了，回家和父亲种一辈子茄子。后来，他真的回家种茄子去了。在京都呆了半个月，城市的干净整洁，人们的高尚品德其实没有给我太深刻的印象，反而是遍布在整个城市的神社让我很是吃惊。在国内，现在连公园都变成了多么奢侈的东西，更不用说在大多数无神论者的国人眼中这丝毫不能带来收益的神道了。日本文化更多的是形式主义，与百花争艳相比，他们更喜欢樱花凋落的凄美。日本四周都是海，自然灾害频发，他们看到的是充满绝望色彩的海平线，与此相比，中国的自然条件要优越的多，我们看到更多的是充满希望色彩的地平线主义，大行其道的是说服文化。或许，正因为国人内心无所畏惧，所以现在的社会底线一次一次的失守。无所敬畏，所以无所不用其极，从这个层面上来看，我们要意识到自己是多么的幸运，在享受着多么优越的自然条件，多么丰富的物产，多么稳定的自然环境。

在日本有很多的以鬼为主题的艺术表演题材，并且有很多让人体验的鬼屋等，同时，据我所知，日本的鬼片拍的是最让人发自内心的恐怖与害怕的。有所畏惧，才能让人守住底线。

日本社会制度是非常人性化的，在社会设施方面，针对不方便者有非常严格的法律来保证其相应的权利。同时，日本人的细心让人非常的赞叹，日本的塑料口袋是黄色的，原因是，乌鸦看不见黄色的口袋。同时日本人的热心从负责赴日留学的负责人的介绍那里就能看出。很多同学问她赴日留学是否通过中介能够有较高的成功率，她这样说的：大家在学校一定要好好读书，有好的GPA，赴日申请的材料拿给我，我帮大家改，我最希望能够帮助那些家里比较贫困，但是自己又认真上进的学生。这句话她前后总共强调过三四次。

日本在二战之后，能够有如此飞速的发展，和他们上一辈的国民有很大的关系。在京都的半个月里，让我最感到意外的是，由于我不会日语，在京都问路都是用英语。基本上日本的年轻人都不愿意开后说英语，或许是因为他们觉得自己的英语口语不够好，反倒是日本七八十岁的老年人，给我印象最深刻的有两个，第一个是我刚到日本招不到住宿的地方时，主动带我们找这个地方的老婆婆。她已经85岁了，当时在学习日本国画，我们就很好奇这其中的原因，她就说，不愿意输给年轻人。另外一个是早上很早在公交车站牌，我想去清水司，但是不确定路线，在站牌只有一个老婆婆，于是乎只有硬着头皮问，不想因为老婆婆不懂英语而难堪，所以我就拿着地图用手指着目的地，希望她能给我指一下路线。让我吃惊的是，她说了一句，map？我吓到了，反应了一下开心的和老婆婆交谈起来。老婆婆告诉我在飞鸟町换乘，就能到了。我研究了一下地图，发现可以直接坐到飞鸟町的下一站，也就是京都大学门口，去那里吃个饭，然后再过去。于是，在飞鸟町那里，我就没有下，就在这个时候，我听到后面有人急匆匆的跑过来，回头一看原来就是那个老婆婆，老婆婆告诉我，就是这一站下去换乘，于是乎，我就很感动的下去了，然后走到了京都大学门口吃得饭，随后才去了清水寺。

日本经历过经济发展时空气质量的恶化，而治理空气质量，日本花了40年，我想，中国，如果不转变发展思路，40年也是很难做到的。当日本经济泡沫严重时，东京的房价也让年轻人叫苦不迭，因为按照工资收入，一辈子都买不起一套房，结果，后来经济泡沫破裂，房价急速下坠，随后就是日本一直至今的失落的20年。

但是有一个问题，日本一直很重视。日本对历史文化的保护，这是我们难以想象的。许老师讲了这样一个故事，有一个浙江大学的建筑学教授，主要钻研唐宋时代的建筑，为了找到和历史资料中一致的建筑古迹，他在全国各地寻觅几十年也未曾见过。一个偶然的机会，他到京都旅游，当他第一眼看到京都的一个普通的桥时，突然激动的流泪了，他说到：这就是我找了这么多年的原迹，不信的话，我拿尺子量给你看。诸如此类，如本源自中国的全木制建筑东大寺等，不胜枚举。在去成都读书之前，我在CCTV上知道了成都的宽宅巷子，所以一到成都，我就先跑到那里去膜拜膜拜，想目睹下这个天府之国的历史韵味。但是，就像现在所有的古镇及名人故居一样，它依然充满的是商业的气息。我到一个地方，最先想去的就是博物馆，了解历史，才能看清昨天我们来时的路，也能知道，我们不过是历史的过客，早晚也沉睡于历史的尘埃之中。但是，在博物馆，我看到的完整文物很少，大多数的文物，尤其是石制的雕塑，几乎绝大多数都没有头部，这要归功于历史的盗墓者，他偷走的是前人留给我们的共同记忆，悲乎！

日本现在有1.27亿人口，但是现在年轻人丁克现象比较严重，如果想维持好的经济发展势头，按照现在的人口规模发展速度是不够的，因此，他们局安思危，开始逐步的放开移民政策，接受外国的优秀人才。并且，有研究数据显示，一个国家的外来人口只要不超过10%，整个社会就是稳定的，否则，很容易出现如欧洲存在的种族歧视等外来移民问题。主要分两部走：

  • 首先提出了旅游兴日的口号。希望能够吸引越来越多的外国人赴日旅游，他们当初提出的口号是在2012年达到年总数1000万的规模，但是由于海啸等自然灾害的原因，去年赴日旅游的外国人只有700万左右。其实，这是他们为移民政策放开做的前期准备。
  • 开展了本科联合培养2+2.5等政策，在4.5年的时间里，就可以拿到两个国家两所学校的文凭，这其中的0.5，没有课时安排，纯粹是给毕业生留下半年的时间在日本找工作。同时，现在越来越多的日本企业开始雇佣外国员工，这也是在响应国家号召。

于是乎，现在出现了越来越多的归化人。选择一个国籍其实只是一种形式，关键是，自己内心真正认同的是哪一种文化，否则，就像是国家选主席一样，自己不care，因为care也改变不了什么，和自己也没有关系，没有存在感。

2 漫画

活动的第二部分请来了中国著名的漫画家胡蓉，胡蓉在中国连环画兴盛的时候开始接触画画，很小就获得了中国连环画的大奖，随着连环画在国内的逐渐没落，她开始走向漫画的道路，并在26岁的时候，第一位以艺术交流的身份赴日学习，并且获得了不错的成绩，现在在日本与中国均有工作室。她强调，自己赴日本的时候，世界观已经形成，因此在日本，绘画技巧的学习并不是最主要的，因为她的内心已经很难被重新刻画，但是，这些经历，让她对生活的理解更深厚了，更多彩了。前几天碰上一个清华美院的学生，她非常的为国人做出一部动画片，然后面试者问她为什么不读硕士或者博士，她是这样说的：我没有生活，我每天的生活就是13个人，因为清华美院她们专业每年只招13个人，必须有生活，才能有画的灵魂。

当谈到中国漫画的未来时，胡蓉提到了一个日本学者的看法：中国的漫画会向当初的连环画一样，最终走向的是艺术的道路，就像是美术，而不会走上商业的道路。因为漫画的本质意味着快速的传播与复制。具体连环画的没落我不太清楚，但是，在我看来，就像是中国的作家的生存现状一样，每一个文化人在当前的大环境下都是很难生存的，所以，漫画应该也是如此。

如果高中毕业就想赴日本都漫画专业，这是比较有难度的：

  • 日本公立大学漫画专业设置很少，大多数均为私立大学。这意味着拿奖学金的机会很少。
  • 如果要赴日本读本科，日语最起码要过四级，最好要过2级。

3 赴日读博

  • 建议给日本教授写书信，而不是电子邮件。据说是因为很多学校的邮箱会block邮件，导致老师收不到邮件。研究计划是非常被看重的。
  • 如果拿到文部省奖学金是非常好的，这样就可以联系日本最好的学校。
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 语音技术沙龙 »

Hide Comments

comments powered by Disqus
posts

Latest

2013-03-17 日本大使馆活动见闻 日本 生活

诗词

左宗棠题江苏无锡梅园 - kamelzcs's library

左宗棠题江苏无锡梅园

Posted on 2013-11-29 02:48:25 +0900 in 诗词 诗词

《左宗棠题江苏无锡梅园》

　　发上等愿，

　　结中等缘，

　　享下等福，

　　择高处立，

　　寻平处坐，

　　向宽处行。

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | Install solarized color theme »

Hide Comments

comments powered by Disqus
posts

Latest

2013-11-29 左宗棠题江苏无锡梅园 诗词

语音

语音技术沙龙 - kamelzcs's library

语音技术沙龙

Posted on 2013-03-17 05:18:21 +0900 in 语音 语音 趋势 大规模机器学习

1 报告内容

第一次在帝都现场参加技术talk的沙龙，比学校的talk要应用性实际的多。

第一个报告是百度语音部门负责人贾磊，主要讲了百度语音搜索在DNN领域的一些经验。百度成立了第一个研究院，Institute of Deep Learning，简称IDL。 由于Deep Learning在语音及多媒体领域面对海量数据的优越性，Google、Miscrosft等公司都开始投入大量的人力、物力做这样一件事情。 没带笔记本过去，凭记忆力列几个关键点。

  • 处理流程为客户端编码、上传、服务器端处理、下放
  • 训练样本为10亿级，如考虑抗噪，会到百亿数量级
  • MS的隐层深度为10层，Google的隐层数目为6层左右，输出层为9000维左右
  • SGD（随机乱序），异步SGD，利用近似二阶梯度i信息为训练中重要方法
  • 节点间通信的带宽为主要瓶颈
  • 单个GPU核的计算能力相当于未优化的CPU核的400～500倍
  • Google有chrome，所以可以在浏览器里加入语音的采集模块，百度没有多媒体采集的客户端，很受限制。

第二个报告是IBM中国研究院的秦勇老师。分享了IBM在语音处理方面的进展，主要是大的picture

  • Itrans（IBM speech transcription server）能够将视频中的语音翻译成文本信息。这个应用在国外的客服领域应用较多，主要是在金融等行业。除此之外，对于很多talk形成文本话非常有意义
  • 讲解了Watson背后的技术DeepQA，虽然Watson目前只应用在娱乐节目上，但是可以将其扩展到如医疗等方向上，因为医学的知识不断的发展，而医生整理知识的工作是可以由Watson代替的
  • 分享了邮件的主题可视化，增加了直观性

提出了几个有意思的点子：

  • 有人在考虑实现如雅思、托福类的口语自动判卷。IBM没有做过商用，但是针对印度的口音做过类似的应用。IBM表示没有考虑语义，看来语义还是很难做的。如果这个效果好，简直可以大赚一笔
  • 可以实现学习如希特勒的说话特征，然后自动的根据特点生成语音。这个略犀利，如果做好了，以后接电话要小心了。
  • 通话质量的可视化

感想：

  • DNN比拼的简直是工程实现能力，架构才是王道啊，机器+架构实现+数据源 是真正的瓶颈
  • 有想法，有技术，敢闯的人在帝都有这种交流的机会真是不错
  • 百度的浏览器、输入法等入口工具都起步太晚，导致了数据上的先天缺陷
  • 技术的交流是必须的，故步自封是要吃苦头的
----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | 初体验 »

Hide Comments

comments powered by Disqus
posts

Latest

2013-03-17 语音技术沙龙 语音 趋势 大规模机器学习