Feeds:
Posts
Comments

Archive for the ‘Uncategorized’ Category

Here is a problem to solve:

Open windows notepad and start with a blank document. At one step, you can choose to type one of
the four below on the keyboard:
“A” “CTRL+A” “CTRL+C” “CTRL+V”

What is the maximal number of A’s you can have in the notepad after 10 steps?

Since each step has 4 options, 10 steps will generate 410 = 1,048,576 key stroke combinations. For each combination, we calculate the number of A’s, and find the combination that results in the maximal number.

In order to calculate the number of A’s for a combination, we need to maintain a state that consists of the current number of A’s, the number of A’s in the clipboard, and whether all text is selected.

For each key stroke in a combination, we determine the next state based on the current state and the key stroke. For example, when A is pressed, if the text is all selected, the number of A’s becomes 1 and the text is not all selected; if the text is not all selected, the number of A’s increases by 1 and the text becomes unselected.

We can define a function that takes a state and a key, and returns a new state.

type Key =
    | A
    | CtrlA
    | CtrlC
    | CtrlV

type State = { number: int; numberCopied: int; allSelected: bool }

let keyStroke state key =
    let a state =
        match state.allSelected with
        | true -> { number = 1; numberCopied = state.numberCopied; allSelected = false }
        | false -> { number = state.number + 1; numberCopied = state.numberCopied; allSelected = false }

    let ctrlA state =
        { number = state.number; numberCopied = state.numberCopied; allSelected = true }

    let ctrlC state =
        match state.allSelected with
        | true -> { number = state.number; numberCopied = state.number; allSelected = state.allSelected }
        | false -> { number = state.number; numberCopied = 0; allSelected = state.allSelected }

    let ctrlV state =
        match state.allSelected with
        | true -> { number = state.numberCopied; numberCopied = state.numberCopied; allSelected = false }
        | false -> { number = state.number + state.numberCopied; numberCopied = state.numberCopied; allSelected = false }

    match key with
    | A -> a state
    | CtrlA -> ctrlA state
    | CtrlC -> ctrlC state
    | CtrlV -> ctrlV state

We defined a sub-function for each key stroke option, and call them depending on the key passed in.

Given a combination of key strokes, how do we calculate how many A’s generated? We can use the fold function.

let evaluate combination =
    let state = combination |> List.fold (fun state k -> keyStroke state k) { number = 0; numberCopied = 0; allSelected = false }
    state.number

For each key stroke in the list, the keyStroke function is called to transit to the next state, with { number = 0; numberCopied = 0; allSelected = false } as the initial state. The number field of the last state will be the number of A’s accumulated.

Once we have the combinations, we can pipe the combinations into the Seq.fold function to find the answer. The curr value is the current combination which is a tuple of the key list and the number of A’s the key list generates. The max value is the combination that has the biggest number of A’s so far. The final output value will be the answer.

let answer = 
    combinations()
    |> Seq.fold 
        (fun max curr -> 
            let (_, number) = curr
            let (_, maxNumber) = max
            if maxNumber < number then
                curr
            else
                max
            ) ([], 0)

Now the only thing missing is how to generate those key stroke combinations. There are several options:

Option 1, using computation expression

We can define a workflow builder class, named Solver, that implements the Bind and Return methods.

type Solver() =
    member this.Bind(xs, f) =
        xs
        |> List.map (fun x -> f(x))
        |> List.concat
    member this.Return(x) = [x]
    member this.Delay(f) = f

The Bind method returns a new list by applying the f function to each element of the given list. The Return methods just convert an element to a list.

We can then find all combinations with the following code:

let keyOptions = [ A; CtrlA; CtrlC; CtrlV ]

let solver = Solver()

let combinations = solver {
    let! k0 = keyOptions
    let! k1 = keyOptions
    let! k2 = keyOptions
    let! k3 = keyOptions
    let! k4 = keyOptions
    let! k5 = keyOptions
    let! k6 = keyOptions
    let! k7 = keyOptions
    let! k8 = keyOptions
    let! k9 = keyOptions

    let keys = [k0;k1;k2;k3;k4;k5;k6;k7;k8;k9]
    let state = keys |> List.fold (fun state k -> keyStroke state k) { number = 0; numberCopied = 0; allSelected = false } 
    return (keys, state.number)
}

The code is pretty easy to read once you understand how computation expressions work. I don’t quite like the fact that I had to write 10 let! bindings.

Option 2, using 2 bits to represent a key option

Since there are 4 key options, we can 2 bits to represent all key options, and 20 bits to represent all key combinations meaning we can use the numbers from 0 to 0xfffff to represent all key combinations of 10 steps with each step having 4 options. In the following code, the toCombination function converts a given number of a list of Keys. For each number from 0 to 0xfffff, we call toCombination to convert the number to a list of Keys and generate a sequence of lists of Keys using the sequence expression.

let keyOptions = [| A; CtrlA; CtrlC; CtrlV; |]

let toKey n =
    keyOptions |> Array.item n

let toCombination length number =
    let mask = 0x3
    [0..(length-1)] |> List.map (fun i -> ((number >>> i * 2) &&& mask |> toKey))

let allCombinations = seq {
    for i = 0 to 0xfffff do
        let c = toCombination 10 i
        yield (c, c |> evaluate)
}

The code is very simple, but what if, for example, there are 5 key options whereby using 3 bits is more than enough to represent 5 options?

Option 3, using a number system

We can generalize option 2 by using a number system with any base. Let’s say we want to have 10 steps and 5 key options, there will be totally 510 combinations. We convert each number from 0 to 510 to a base 5 number with 10 digits, each of which represents a key option.

let keyOptions = [| A; CtrlA; CtrlC; CtrlV; |]

let toKey n =
    keyOptions |> Array.item n

let toBase (b: int) (number: bigint) =
    let rec getDigits (n: bigint) digits =
        let bb = b |> bigint
        if n >= bb then
            let d = n % bb |> int
            let nn = n / bb
            getDigits nn (d::digits)
        else
            (n |> int)::digits

    getDigits number []
 
let toCombination b length (number: bigint) =
    let digits = toBase b number
    let diff = length - (digits |> List.length)
    match diff with
    | 0 -> digits
    | 1 -> 0::digits
    | _  -> [0 .. diff - 1] |> List.fold (fun s _ -> 0::s) digits

let allCombinations optionCount length = seq {
    let max = (double)optionCount ** (double)length |> bigint

    let _toCombination = toCombination optionCount length

    for i in 0I .. max do
        let c = _toCombination i |> List.map (fun i -> toKey i)
        yield (c, c |> evaluate)
}

The implementation is similar to option 2. The only difference is how to extract the digits from a number.

Conclusion

There are many ways to generating the key combinations. In fact, we can also use List.collect with List.map in a recursive function to generate the all combinations:

let allCombinations length options = seq {
    let rec expand currLength combinations =
        match currLength = length with
        | true -> combinations
        | false -> 
            expand (currLength + 1) (options |> List.collect (fun o -> combinations |> List.map (fun c -> o::c)))

    yield! expand 1 (options |> List.map (fun o -> [o])) 
}

I’ve gained more knowledge about F# and functional programming in general when I was exploring various solutions. I particularly like the fold function which allows me to mutate a state in purely functional way.

By the way, the answer of the problem is:

val answer : Key list * int =
([A; A; A; A; CtrlA; CtrlC; CtrlV; CtrlV; CtrlV; CtrlV], 16)

Thanks for reading!

Advertisements

Read Full Post »

I was given a puzzle to solve recently. The puzzles is a cryptarithmetic problem: 5’s twelve + thirty = ninety.

T W E L V E
T W E L V E
T W E L V E
T W E L V E
T W E L V E
T H I R T Y
————
N I N E T Y

Each letter represents a unique number from 0 to 9.

As a software engineer, I naturally wanted to solve this problem by writing a program, and I decided to use F#, in functional way.

Here is the code I wrote:

open System

let digits = [0..9] |> Set.ofList

let remainingDigits removedDigits =
    Set.difference digits (Set.ofList removedDigits)

let toNumber digits =
    digits |> List.fold (fun number i -> number * 10 + i) 0

type PuzzleSolver() =
    member this.Bind(xs, f) =
        xs
        |> Set.map (fun x -> f(x))
        |> Set.filter (fun x -> x |> List.isEmpty |> not)
        |> Set.toList
        |> List.concat

    member this.Return(x) = [x]
    member this.ReturnFrom(x) = x

let solver = PuzzleSolver()

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v); 
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

solutions |> List.iter (fun (l, v) -> printfn "%s = %d" l v)

And the following is the result copied from the F# Interactive console of Visual Studio:

T = 1
W = 3
E = 0
L = 7
V = 6
H = 9
I = 4
R = 2
Y = 5
N = 8

val digits : Set<int> = set [0; 1; 2; 3; 4; 5; 6; 7; 8; ...]
val remainingDigits : removedDigits:int list -> Set<int>
val toNumber : digits:int list -> int
type PuzzleSolver =
    class
        new : unit -> PuzzleSolver
        member
            Bind : xs:Set<'c> * f:('c -> 'd list) -> 'd list
                when 'c : comparison and 'd : comparison
        member Return : x:'b -> 'b list
        member ReturnFrom : x:'a -> 'a
end

val solver : PuzzleSolver

val solutions : (string * int) list =
[("T", 1); ("W", 3); ("E", 0); ("L", 7); ("V", 6); ("H", 9); ("I", 4);
("R", 2); ("Y", 5); ("N", 8)]
val it : unit = ()

Let’s look at the F# code. The digits value is a set of 10 integers from 0 to 9. The remainingDigits function removes the given integers from the digits set and returns the remaining digits. The toNumber function converts the given digits to an integer.

At the heart of the algorithm is the PuzzleSolver computation expression. The Bind method takes a Set and a function that maps a value to a list, and returns a list.

member this.Bind(xs, f) =
    xs
    |> Set.map (fun x -> f(x))
    |> Set.filter (fun x -> x |> List.isEmpty |> not)
    |> Set.toList
    |> List.concat

The Bind() method pipes the given set to the Set.map function to create a set of list by mapping each element in the set to a list by calling the f function passed in. It then pipes the set of lists to Set.filter to create a new set by removing all empty lists. The new set of lists is then converted to a list of lists, which is passed to List.concat to flatten to a list.

The Return method just wraps the given value as a list. And the ReturnFrom method just returns the given value.

With the PuzzleSolver computation expression, we can solve the puzzle with following code:

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

The code essentially says that:

Let the identifier t be one of the digits from 1 to 9,

Let the identifier w be one of the digits from 0 to 9 except for t,

We bind each of the 10 identifiers to a different digit, we then calculate the values of TWELVE, THIRTY, and NINETY, if the 3 values meet the condition, which is TWELVE * 5 + THIRTY = NINETY, we return a list of pairs of a letter and the digit it represents, otherwise, an empty list is returned.

The let! Expression is just a syntax sugar for the Bind method. So

let! t = remainingDigits [0]

is essentially translated into

solver.Bind(remainingDigits [0], (fun t -> …) )

And the whole solutions expression is translated into nested method calls to the solver.Bind() method:

let solutions =
    solver.Bind(remainingDigits [0], fun t ->
    solver.Bind(remainingDigits [t], fun w ->
    solver.Bind(remainingDigits [t; w], fun e ->
    solver.Bind(remainingDigits [t; w; e], fun l ->
    solver.Bind(remainingDigits [t; w; e; l], fun v ->
    solver.Bind(remainingDigits [t; w; e; l; v], fun h ->
    solver.Bind(remainingDigits [t; w; e; l; v; h], fun i ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i], fun r ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r], fun y ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r; y], fun n ->

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        solver.ReturnFrom([ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                            ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ])
    else solver.ReturnFrom([])
))))))))))

This is not too difficult to understand compared to the nested for loops if we were to solve it in imperative way.

let solutions2 =
    for t in (remainingDigits [0]) do
    for w in (remainingDigits [t]) do
    for e in (remainingDigits [t; w]) do
    for l in (remainingDigits [t; w; e]) do
    for v in (remainingDigits [t; w; e; l]) do
    for h in (remainingDigits [t; w; e; l; v]) do
    for i in (remainingDigits [t; w; e; l; v; h]) do
    for r in (remainingDigits [t; w; e; l; v; h; i]) do
    for y in (remainingDigits [t; w; e; l; v; h; i; r]) do
    for n in (remainingDigits [t; w; e; l; v; h; i; r; y]) do

        let TWELVE = toNumber [t;w;e;l;v;e]
        let THIRTY = toNumber [t;h;i;r;t;y]
        let NINETY = toNumber [n;i;n;e;t;y]

        if (TWELVE * 5 + THIRTY = NINETY) then
            printfn "TWELVE=%d, THIRTY=%d, NINETY=%d" TWELVE THIRTY NINETY

Read Full Post »

I participated in a Lego Robot Competition recently, and our team of 5 persons won the first prize. Our robot successfully accomplished its mission: picking up a treasure, a Lego block in red color, and putting it in the dropping area inside a maze, exiting the maze, and hunting for the next treasure.

Components of the robot

robot001

Figure 1. The Lego Robot

The robot consists of a Samsung Galaxy S4 Android phone, a Rockwell MicroLogix 830 controller, 3 Lego motors, a Xiaomi power bank, and several infra-red distance sensors. The phone connects to the MicroLogix controller via an USB OTG cable, an USB to serial converter, and a serial cable. The communication protocol between the phone and the controller is MODBUS over serial line.

The Android app is the brain of the robot. It captures pictures periodically to detect treasures and the 3 mazes (in blue, green and purple color respectively) and reads the values of the sensors to determine what to do next. It sends commands to the controller to make a move, a turn, pick up or put down a treasure. The controller is not entirely passive: it can stop the robot when it detects that it is too close to a wall.

The PLC (Programmable Logical Controller) logic running in the controller uses PID to control the motors to make accurate moving or turning.

The Android app

The Android app is built on top of 2 open source libraries: OpenCV (http://opencv.org/) and the jamod Modbus library
(http://jamod.sourceforge.net/). The OpenCV library is used to capture pictures and detect objects from the pictures; while the jamod library is used to send commands and read sensor values to and from the MicroLogix controller. (I’ve made some modification to the jamod library to make it working with Android serial driver.)

At the heart of the Android app is the Robot class. A Robot object has a RobotCommander for sending commands to the MicroLogix controller, a RobotSensors object for reading sensor values, several ObjectDetectors for detecting treasures, mazes, outer walls, and the dropping area.

robot002

Figure 2. The class diagram of the Robot class.

State machines

The behavior of the Robot is controlled by the state machines. The top level state machine has 5 states: Initial, Initialized, Running, Paused, and Stopped. After the Robot is initialized it can be put into the Running state. When in the Running state, it can be Stopped, it can also be Paused and then resumed to the Running state.

robot003

Figure 3. The top level state machine

The Running state itself is a state machine that has 9 sub-states, as shown in Figure 4: FindingTreasure, ApproachingTreasure, PickingTreasure, FindingMaze, ApproachingMaze, FindingMazeEntrance, FindingDropArea, DroppingTreasure, and ExitingMaze.

The Robot first searches for a treasure. Once a treasure is found, it moves towards the treasure, and picks it up. It them searches for a maze, approaches it, and finds the entrance. Once it is in a maze, it looks for the drop area, drops the treasure, exits the maze, and starts over again.

robot004

Figure 4. The sub-state machine of the Running state

Each sub-state corresponds to a state machine, which we call a Sequence. Figure 5 shows the state diagram of the Finding Treasure state.

robot005

Figure 5. Finding Treasure sequence

The implementation of state machines

Two interfaces, IStateMachine and IState, as shown in Figure 6, are defined for implementing the state machines. IState represents a state. Upon entering or exiting a state, the enter() or exit() method is called respectively. The move() method will be called one or more times when the state is active to allow the Robot to make a move. IStateMachine represents a state machine. It can change the current active state and have the current state to make a move.

robot006

Figure 6. IStateMachine and IState

Figure 7 shows all classes that implement the IStateMachine interface. Class RobotStateMachine implements the top-level state machine as shown in Figure 3 and class RobotRunningStateMachine implements the sub-state machine as shown in Figure 4. Class RobotRunningSequence is the base class of sequences. Each sub-class of RobotRunningSequence corresponds to a state of the sub-state machine.

robot007

Figure 7. State machines

When the Robot object is in the Running state, the continueMission() method is called periodically, which calls move() on the RobotStateMachine object, which calls move() on the current state, Running, which calls move() on the RobutRunningStateMachine object, which calls move() on the current sequence. If the m_nextState member variable is not null, it calls changeState(), which calls exit() on the current state, makes m_nextState the current state, and calls enter() on it. It finally calls move() on the current state, which would most likely calls sendCommand on the Robot object to send a command to the controller.

robot008

Figure 8. State machines sequence diagram

The states of a state machine are implemented using a Java enum, with each enum field representing a state. The following code shows how the top-level states are defined.

public enum RobotState implements IState {
    Initial {
        @Override
        public void enter(IStateMachine machine) {
        }
        @Override
        public void move(IStateMachine machine) {
            machine.robot().initialize();
            machine.changeState(Initialized);
        }
        @Override
        public void exit(IStateMachine machine) {
        }
     },
     Initialized {
        @Override
        public void enter(IStateMachine machine) {
            machine.robot().ensureArmAtHome();
        }
        @Override
        public void move(IStateMachine machine) {
            // wait
        }
        @Override
        public void exit(IStateMachine machine) {
        }
 
    },
    Running {
        @Override
        public void enter(IStateMachine machine) {
            m_runningMachine.afterResume();
            machine.robot().log("Enter Running state", 2);
        }
        @Override
        public void move(IStateMachine machine) {
            m_runningMachine.move();
        }
        @Override
        public void exit(IStateMachine machine) {
            // do nothing
        }
 
    }, 
    Paused {<
        @Override
        public void enter(IStateMachine machine) {
            m_runningMachine.beforePause();
        }
        @Override
        public void move(IStateMachine machine) {
            machine.waitForResume();
        }
        @Override
        public void exit(IStateMachine machine) {
        }
 
    },
    Stopped {
        @Override
        public void enter(IStateMachine machine) {
            machine.robot().sendCommand(RobotAction.Stop);
        }
        @Override
        public void move(IStateMachine machine) {
            machine.robot().sleep(200);
        }
        @Override
        public void exit(IStateMachine machine) {
        }
    }
}

ThreadingEvery enum field is in fact a class. This makes the code more concise by not having to explicitly define a Java class for each state.

In an Android app, if the UI thread is blocked for more than 5 seconds the app will be forced to be stopped. To avoid running into this scenario, the entire state machine is running on a worker thread. When a Robot object is created, a work thread is created with a Runnable object whose run() method periodically calls the continueMission() method, which calls the move() method on the RobotStateMachine object.

In the TestSequenceActivity, a RobotTask class, inheriting from AsyncTask, is defined to test individual sequences using a worker thread.

In order to avoid the changeState() and move() methods of RobotStateMachine to be called by the UI thread, the methods throw an exception if the calling thread is the main thread.

public void move() {
    if (Looper.myLooper() == Looper.getMainLooper()) {
    throw new RuntimeException("move() cannot be called by the main thread");
}
…
}

Debugging

When the Android app is running, we cannot use Eclipse to debug the app as the USB port is used to connect to the controller. We chose to use log to help us understand what is going on. We create some Android Activities specially for debugging, e.g. an Activity for testing Modbus communication, an Activity for testing sending commands to the controller, and an Activity for testing individual sequences. The log of the debugging Activities provides much detailed information, while the log of the run mode Activity, RobotActivity, provides only important information.

An interface named IRobotLogger is defined for the Activities to implement to display logging information. When the log() method is called, if the logging level is equal to or higher than the lowest  logging level it is interested in, it appends the string passed in to the TextView.

Since the state machines are all running on a worker thread, the log() method cannot directly call the append() method on the TextView, instead it should send a request to the UI thread to do so by calling the runOnUiThread() on the Activity.

public void log(final String msg) {
    TestSequenceActivity.this.runOnUiThread(new Runnable() {
        public void run() {
            TextView logDisplay = (TextView) findViewById(R.id.text_log);
            logDisplay.append(msg + "\n");
        }
    });
}

Points of Interest

Adopting the State design pattern makes our code much easier to understand and debug. Even though only myself was working on the Java code debugging, the well understood behavior of each state machine plus the detailed log allow other team member to help me understand what was going on, and thus greatly shorten our debugging time.

When we designed the classes of the model, we had unit-testability in mind, although we hadn’t written much unit tests, as we were implementing the App in a rush. We defined some interfaces, such as IRobotCommander, IRobotSensors, to make them mockable.

Debuggability is the key for us to develop the app in such a short time with relatively good quality. The activities developed specially for debugging help us troubleshoot the issues we encountered quickly.

Using the Modbus protocol for the communication between the phone and the controller removes a lot of burden in both the Android app and the PLC code compare with using serial port communication directly.

If I had a chance to develop a similar app, I would consider developing a DSL (Domain Specific Language) for defining the sequences: defining how the states should be changed depending on the sensor values and the object detection result. This would allow non-Java developers to define and debug the sequences. I would also enhance the object detection by utilizing more OpenCV functionality.

 

 

Read Full Post »

Simple Made Easy

We often use ‘simple’ and ‘easy’ interchangeably. This presentation given by Rich Hickey makes it clear about the difference between the two words. Simple is objective. Easy is relative. Some thing may be very easy to someone, but very hard to others. When we say something is easy, it might be because we are familiar with it. It doesn’t necessarily means it is simple.

http://www.infoq.com/presentations/Simple-Made-Easy

 

 

Read Full Post »

New books

Received my books ordered from Amazon:

Implementing domain-driven design, by Vaughn Vernon,
ng-book, by Ari Lerner

Read Full Post »

发现数学美

 随着小女儿升入中学,我对数学的兴趣也从小学水平提升到中学水平;-),以做好被提问的准备。如果说小学数学主要是数的加减乘除,中学代数主要是关于数之间的关系和规律,如函数,如勾股定理等,而微积分则是函数之间的关系。

在小学数学中,一个数是数轴上的一个点。数的加减是一个数在数轴上的移动,数的乘除是一个数在数轴上的缩放。
中学数学的一个理解难点是虚数。虚数这个词有点让人望而生畏,事实上复数是数从一维到二维的扩展。而虚数只是与实数垂直的另一个数轴。一个实数是一维数轴上的一个点,一个复数是二维数平面上的一个点。所以一个复数就是一个二维座标点。复数的加减是沿实数轴和虚数轴的位移,复数的乘除是模长的缩放与幅角的加减。
一直以来觉得我们接受的数学教育只是灌输知识,而没有教我们去直观地理解。如果我们知道古人为什么发现并研究圆周率或e,或许更有利于学生理解那些概念,并进而体会数学之美:简单、和谐、奇异。
我最初体会数学之美是中学时发现有不少题可以一题多解。一道题既可以用几何解,也可以用代数解,甚至可以用物理直观去解,如光线总是走最短距离等。而有些解法是那样的简单、巧妙。记得上初三时有一次该我出答案。其中一题是:有两个点A和B在一条直线的同一侧,在该条直线上找一点P使AP加BP的长度最短。我贴出答案后,我的十年同窗亚林找到我说我的答案错了。他在直线另一侧画出A的对称点C,然后在在B和C之间画一条直线,说两点之间直线最短。我一下感受到了一种深深的美感,令我铭记至今。
愿我的女儿也能体会到学习数学的乐趣,发现数学之美。

Read Full Post »

古罗马建筑大师Marcus Vitruvius认为一个好的建筑要达到“稳固(firmness)、实用(usefulness)、赏心悦目(delight)”。把美观放到了极高的位置。Frederick P. Brooks, Jr.在他的著作“The Design of Design”中反复用这三个准则衡量他亲自参与的设计,包括建筑、计算机结构、操作系统、甚至书籍的版面设计。显然他认为这三个准则同样适合于软件。

对用户而言,一个软件不死机、不出错可称之为稳固;能让用户顺利完成其任务可称之为实用;能给用户提供一个简洁、布局合理、色彩搭配和谐的界面或可称之为赏心悦目。然而,这三个特征还有程度的不同,如真正实用的软件要易学易用,能引导用户的操作,为用户提供及时的反馈;使常用的功能容易做,不常用的功能能够做。

就开发人员而言,稳固应该指软件的整体结构相对稳定,在可预见的未来,不会因为增加新功能而导致整体结构不堪重负。实用应指每个模块(module)、每个类(class)、每个函数(function或method)都有其特定功能。模块之间、类之间、函数之间没有功能重叠。开发人员能很快找到他想用的类或函数。赏心悦目应指从结构设计到代码、文档都简洁且风格统一,给人以美感。

唯简单才能达到稳固、实用、赏心悦目。简单才容易扩展。一个已经很复杂的结构是很难再扩展的,所以在扩展软件结构时要慎之又慎。简单才易学易用。简单才容易做到整洁、美观。
无印良品的产品推崇极简设计,去除了一切不必要的加工和颜色,简单到只剩下素材和功能本身。却反而给人们一种结实、易用、美观的感觉。在IT领域,极简设计也越来越流行。Android、iOS和Windows Phone 8在界面设计上都提倡平面化设计(flat UI)。

数学美的特征是简单、和谐、奇异。这似乎也同样适用于软件设计。简单并不易做到。唯有对事物做到高度抽象后才能做到简单。需认真分析所要解决的问题,发现其背后的逻辑规律,才能使设计简化。软件设计师切忌卖弄聪明,在设计中添加不必要的元素。要知道很多软件项目失败的根本原因是没有控制好软件的复杂度。当然追求简单不能以牺牲功能为前提。
光简单还不够,还要有统一的风格,给人以整洁和谐的美感。统一的风格也能使设计更易于理解。

如果一个设计在简单、风格统一的基础上能出人意表,让人耳目一新,那就是传说中的上上之作吗?真正好的设计增一分太肥、减一分太瘦。这样的设计若非妙手偶得,便是经过锤炼的设计的精华。似我等普通人就只有通过不断研究前人的设计成果、不断练习来提高自己的设计能力了。

最近几年,我对Eric Evans倡导的领域驱动设计(Domain Driven Design)极感兴趣,并有意识地在我开发的几个软件上应用,觉得获益匪浅。Jeffery Palermo在领域驱动设计的基础上提出了洋葱架构(Onion architecture)的概念。不同于普通的水平层次结构,他认为软件结构应该是球形层次结构:核心是领域模型(Domain Model),向外依次是领域服务(Domain Services),应用服务(Application Services),最外层是用户界面、基础设施(如数据库)。这个结构与地球的结构和细胞的结构是何其相似。如果一个软件结构与自然界中的某种结构相吻合,那这种结构自有其合理之处。我的经验告诉我洋葱架构有助于开发稳定、实用的结构。至于赏心悦目,那就要看我的造化了。

Read Full Post »

Older Posts »