编程语言笔记.md

编程语言笔记

scheme笔记

语言基础

atom: null?, zero?, number?, quote?
list: car,cdr,cons
control: cond else, let, define
s expression = atom or list
lambda expression

重要概念

recursion
tail recursion
continuation
call with current continuation
continuation passing style (CPS)
CPS transform
lazy calculation
collection
closure
coroutine
lambda recursion
Y combinator
close variable, free variable

c 语言

struct
- aligin
- tail zero array
- function pointer members
function
- declare
- function pointer
number
string
macro
typedef
trait
sizeof
typeof
offsetof,containof
size and malloc

c++ 语言

basic
- const
- type cast
- io
- Pointers
class
- default functions
- function override
- const
template
- function template
- class template
- specification
- partial specification
- concept lite
- template template
- variant template arguments
- trait
stl
- functor
- allocator
- container
- algorithm
- iterator
- adaptor
c++ 98/03/11/14
More C++ Idioms

csharp 笔记

核心概念

lambda expressions, delegate, event, Action<T> and Func<T>
anonymous types
closure
extension methods, extension attributes
implicity typed local variable
object and collection initializer
query expressions
expression tree
linq to object,linq to xml, linq to sql, linq to anything
LINQ
Task<T>, async/await
IEnumrable<T>, IComparable<T>, IQueyable<T>, IObserverable<T>
dynamic

Java

Basic

Haskell

Program Practice

Values
- Communication(Readable)
- Simplicity
- Flexibility
Principles
- Local Consquences
- Minimize Repetition
- Logic and Data Together
- Symmetry
- Declarative Expression
- Rate of Change
Cost of software
- Cost of Develop
- Cose of Maintain
  - Cost of Understand
  - Cost of Change
  - Cost of Test
  - Cost of Deploy

Y Combinator 简析

#####什么是Combinator

首先必须是个lambda表达式
其次所有的变量都必须是lambda表达式的参数，也就是没有自由变量

例子

(lambda (x) x) //是
(lambda (x) y) //不是，有自由变量y
(lambda (x) (lambda (y) x)) //是
(lambda (x) (lambda (y) (x y))) //是
(x (lambda (y) y)) //不是，非lambda表达式
((lambda (x) x) y) //不是，非lambda表达式

#####如何用lambda做递归

传入自己(待递归的lambda表达式)的拷贝。
延迟（传入自己拷贝后的lambda表达式在调用自己拷贝处的）求值，以免整个lambda还没被使用就死递归在无限求值上。

所以这样得到的lambda递归会具有如下形式

(define (part-factorial self)
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1)))))) //此处f是(self,self)，如果不延迟求值，会无限递归
     (self self)))

(define factorial (part-factorial part-factorial))

#####剥离Y Combinator，以便复用

(define (Y f)
    ((lambda (x) (x x))       //这个是对下面那个lamba的(x x)
     (lambda (x) (f (x x))))) //这个是对目标lambda的(x x)

这种剥离只是为了复用，如果你不想复用，每次都像上面的factorial一样写那个结构也可以，理解这点才是重点。这就跟C语言的宏一样，很多用宏做的东西，你展开后看很简单，用宏只是在理解的基础上的复用。学习算法和数据结构也是一样，泛型容器和算法只是在你理解基础上的复用，但你要会手写才真的知道其中关键点。复用只是为了减少代码量，手写结构，并理解才是基础。

#####Y Combinator可以写成更直观：

(define (Y f)
    ((lambda (y) (y y))       //这个是对下面那个lamba的(y y)
     (lambda (x) (f (x x))))) //这个是对目标lambda的(x x)

全部都是x的那个版本，只是为了装代数符号的逼格而把上面的小y也写成x绕晕你。

#####Y Combinator刚好符合函数不动点性质

(Y f) = (f (Y f))

Monad

描述

In pure functional programming languages you aren't allowed to cause side effects. The only way a function can 'interact' with the outside world is to return something. So if you have a function that needs to return a number, but has a certain side effect, the only way to do this is to return the number and return some data 'containing' the side effect. But that's a pain in the ass - you have to write all of your code to return multiple values, and you have to write plumbing code to pass these side-effect containing values around. What monads can do is give a uniform API to side-effect containing data so you can just concentrate on the number that you want to return, and have the side-effect carried along automatically in the background. What's neat about monads is the same API can be used for many different problems, not just handling side-effects.

探讨

基于集合论的结构：群、环、域、模、拓扑空间、算子、单子等。唯一目的就是寻找这样的集合，其元素在给定几条公理化操作下，保持某些不变的性质。这样的集合结构上可以建立公理、推导引理、推导定理，使得只要是这种结构的集合，就可以使用这些公理、引理、定理证明其拥有怎样的性质和结论。

单子，正是这样一种结构，只是其刚好被这帮搞lisp的人用在了以函数为元素的集合上，并且这样的一种结构刚好能用解决函数级别的抽象封装问题。想清楚这点，就不至于陷入细节而不知其所以然。

参考资料

Monads in C
Monads in C++
Introduction to Category Theory
[Monoids, Functors, Applicatives, and Monads: 10 Main Ideas] (http://monadmadness.wordpress.com/2015/01/02/monoids-functors-applicatives-and-monads-10-main-ideas/)
a page about call/cc
stackoverflow:what is call/cc
douban:call/cc
wesdyer:cps.net
schemewiki:call/cc
Introduction to Y Combinator

gemire/编程语言笔记.md