Reading Lambda Calculus

Posted on October 28, 2021 by admin

Complex expressions in lambda calculus notation here is hard to parse in the head correctly until the day I started using Dart Language and noticed the connection between => lambda notation and C-style function layout. Here’s what I learned:

The expressions are right-associative because the right-most expression is the deepest nested function
Function application (feeding values to the arguments) always starts from left-to-right because you can only gain entry to a nest of functions starting from the outermost level, peeling it layer by later like an onion. So if applying arg to statement is denoted by (statement arg), the order of input would be (((statement arg1) arg2) arg3)
Names showing up on the parameter list of the nearest layer sticks to it (local to the function) and excludes everybody else (variable shadowing): this means the same name have absolutely no bearing as a free variable or being a free variable anywhere, so you can (and should) replace it with a unique name.

Here’s the calculus syntax in the book:

This example is the function application used above

Here’s where reusing the variable $x$ in multiple places to mean different things gets confusing as hell, and the author (as well as the nomenclature) do not emphasize the equivalence to variable shadowing rules:

This can be rewritten as having

$\lambda w . w^2$
$\lambda z . (z+1)$
$\lambda f . \lambda g . \lambda x.(f (g x) )$

Upon application,

$((\lambda f . \lambda g . \lambda x.(f \quad (g \quad x) ) \qquad \lambda w . w^2) \qquad \lambda z . (z+1))$

$\implies (\lambda g . \lambda x.(\lambda w . w^2 \qquad (g \quad x) ) \qquad \lambda z . (z+1))$

$\implies \lambda x.(\lambda w . w^2 \qquad (\lambda z . (z+1) \quad x) )$

which clearly reads for an input of $x$ , it’ll be incremented first then squared. Resolving further:

$\implies \lambda x.(\lambda w . w^2 \quad (x+1) )$

$\implies \lambda x.(x+1)^2$

Fucking evils of variable shadowing! Not only it makes the code hard to read and reason, it also make the mathematics hard to follow!

Using Dart’s C-style syntax to make chain of lambda functions concrete

Posted on October 28, 2021 by admin

Start with an example lambda calculus expression $f\equiv\lambda x.(y+x)$ . It is:

[programming view] a function with $x$ as an input argument and it uses $y$ from the outer workspace (called a free-variable). f(var x) { return y+x; }
[mathematical view] can also be written as $f(x) = y+x$ where $y$ is seen as a fixed/snapshotted value relative to the expression.

g(int y) => (int x) => y + x

Lambda calculus is right-associative

g(int y) => ( (int x) => y + x )

Unrolling in C-style it will give better insights to the relationships between layers

g(int y) {
  return (int x) { return y + x; };
}

Note that (int x) { return y + x; } is a functor. To emphasize this, the same code can be rewritten by assigning the name f to it and returning f:

g(int y) {
  f(int x) { return y + x; };
  return f;
}

Use the C++11 style syntax so that it doesn’t look like nested function implementation body instead of a functor nested inside a function:

g(int y) {
  var f = (int x) { return y + x; };
  return f;
}

Note that conceptually what we are doing with the wrapper cascade is indeed nested functions. However, in the wrapper, we spit out a functor (which did most of the partial work) so the user can endow/evaluating it with the last piece of needed info/input:

g(int y) {
  f(int x) { 
   return y + x;
  };
  return f;
}

More commonly as seen in Dart docs, this formatting shows a (binder/capturing) wrapper function returning its own nested function:

g(int y) {
  return (int x) { 
           return y + x;
         };
}

Styles for (Lambda) anonymous function (named or unnamed) in Dart Language

Posted on October 27, 2021 by admin

Official Dart docs is sometimes too simple to provide ultimate answers for various language questions. I discoverd an alternative syntax for named lambda here and here. In Dart,

(args) => expr

is the shorthand for

(args) { 
  return expr 
}

So the Lambda-style (C++11) names variable by assigning it to a messy functor type (inferred with var in Dart and auto in C++11):

var f = (args) => expr

Which can also be rewritten using C-style function pointer-like declaration except

the body expr is included (which is not allowed in C),
return must be explicit in curly braces block.
arrow notation => takes whatever the expr evaluates to (which can be null for statements like print)
it’s simply the function name f in Dart instead of pointer (*f) in C

[optional return type] f(args) { 
  return expr;
}

which can be simplified with the arrow operator

[optional return type] f(args) => { expr }

MATLAB repeating arrays (elementwise array replication, interleaved ‘repmat’)

Posted on October 24, 2021 by admin

Since MATLAB R2015b, there’s a new feature called repelem(V, dim1, dim2, ...) which repeats each element by dimX times over dimension X. If N (dim1) is scalar, each V is uniformly repeated by N times. If N is a vector, it has to be the same length as V and each element of N says how many times the corresponding element in V is repeated.

Here are some historical ways of doing it (as mentioned in MATLAB array manipulation tips)

The scalar case (repeat uniformly) can be emulated by a Kronecker product multiplying everything with 1 (self):

kron(V, ones(N,1))

Just replace all the elements b with 1 so we are left with elements of A repeating the way we wanted

Kron method is conceptually smart but it has unnecessary arithmetic (multiply by 1). Nonetheless this method is reasonable fast until TMW finally developed a built-in function for it that outperforms all the tricks people have accumulated over decades.

The vector case (each element is repeated a different number of times according to vector N) is basically decoding Run-Length Encoding (RLE), aka counts to placements, which you can download maturely written programs on MATLAB File Exchange (FEX). There are a bunch of cumsum/diff/accumarray/reshape tricks but at the end of the day, they are RLE decoding in vectorized forms.

There’s a name for almost each recurring problem that we can think of in MALTAB. Before jumping in and implementing your for loop, ask around and try to find the right keyword/terms to describe your problem! >99.9% of the time your problem is not new!

The most odd-ball MATLAB algorithm scenario I’ve ever came across that requires original thought is the ‘Jenga Matrix‘ (I coined the name) while I was working at Stanford University Medical School as a research assistant for MADIT-CRT.

MATLAB’s OOP was not mature at that time, so dataset() objects didn’t surface. The reason for the ‘Jenga Matrix’ was to create ‘sparse cells’ which uses a sparse matrix with non-zero indices mapping to a cell vector so I can make a table (that’s approximately the guts of heterogenous data structure).

As I remove elements of the ‘sparse cell matrix’, I didn’t want holes in it to accumulate so I’ll have to periodically compact the underlying cell vector and shift the indices to reflect the indices after compacting. Normally if you have to mess with these kind of ingenious indexing algorithms, you are working on some generic abstractions/tools rather than the business logic itself.

There’s no ultimate correct way to implement something in MATLAB, but there are tons of bad ways that is strictly worse under all circumstances! Being smart with these little toy (Cody) problems like array manipulation do not really show practical proficiency in MATLAB. Anybody can spend a day or two to solve a genuinely new algorithm puzzle or just ask around in the forums if you run into it once in a blue moon. Who cares if you can do it 5 times faster if it’s just <1% of the development time?

Most of your time should be spent on using MATLAB to succinctly and intuitively describe your business logic (which requires exploring and understanding your project requirements deeply), and hide the boring background work with generic abstractions (e.g. RDBMS and RLE)! People should be able to read your function and variable names and form a clear picture of what your codebase is trying to achieve instead of stumbling over smart-ass idioms that’s not immediately obvious (which should buried in the lowest level of generic tool functions if you had to develop it in-house).

Even a mathematician in Linear Algebra using MATLAB for 40 years doesn’t mean he’s good at MATLAB! The real MATLAB skills are keeping up with MATLAB has to offer for a variety of scenarios relevant to the task at hand (or know enough abstract concepts like functional programming, OOP, database, etc, to be able to find out the right tools quickly), which is a hell lot of knowledge considering MATLAB covered most common scenario imaginable (the vast majority of MATLAB users aren’t aware of the full offerings and used MATLAB the wrong/hard way)!

Data Relationships of Spreadsheets: Relational Database vs. Heterogenous Data Tables

Posted on October 23, 2021 by admin

This blog post is development in process. Will fill in the details missing details (especially pandas) later. Some of the MATLAB syntax are inaccurate in the sense that it’s just a description that is context dependent (such as column names can be cellstr, char string or linear/logical indices).

From data relationship point of view, relation database (RDMBS), heterogenous data tables (MATLAB’s dataset/table or Python Panda’s Dataframe) are the same thing. But a proper database have to worry about concurrency issues and provide more consistency tools (ACID model).

Heterogenous data tables are almost always column-oriented database (mainly for analyzing data) where MySQL and Postgres are row-store database. You can think of column-store database as Struct of Arrays (SoA) and row-store database as Array of Struct (AoS). Remember locality = performance: in general, you want to put the stuff you frequently want to access together as close to each other as possible.

Mechanics:

Concepts	SQL	MATLAB table	Pandas Dataframe

tables	FROM	(work with T)	(work with df)
columns variables fields	SELECT	`T.(field)` `T(:, cols/varnames)`
rows records	WHERE HAVING	`T( cond(T), : )` `T_grp( cond(T_grp), : )`
conditions	NOT IS IN BETWEEN	`~` `==, isequal*()` `ismember()` `a<=b & b<=c`
Inject table to another table	INSERT INTO t2 SELECT vars FROM t1 WHERE rows	`T2(end+(1:#rows), vars) = T1(rows, vars)` (Doable, throws warning)
Insert record/row	INSERT INTO t (c1, c2, ..) VALUES (v1, v2, ..)	`T=[T; {v1, v2, ...}]` (Cannot default for unspecified column*)
update records/elements	UPDATE table SET column = content WHERE row_cond	`T.(col)(row_cond) = content`
New table from selection	SELECT vars INTO t2 FROM t1 WHERE rows	`T2 = T1(rows, vars)`
clear table	TRUNCATE TABLE t	`T( :, : )=[]`
delete rows	DELETE FROM t WHERE cond (if WHERE is not specified, it kills all rows one by one with consistency checks. Avoid it and use TRUNCATE TABLE instead)	`T( cond, : ) = []`

* I developed sophisticated tools to allow partial row insertion, but it’s not something TMW supports right out of the box. This involves overloading the default value generator for each data type then extract the skeleton T( [], : ) to identify the data types.

Core database concepts:

Concepts	SQL	MATLAB (table/dataset)	Pandas (Dataframe)
linear index	CREATE INDEX idx ON T (col)	`T.idx = (1:size(T,1))'`
group index	CREATE UNIQUE INDEX idx ON T (cols)	`[~, T.idx] = sortrows(T, cols)` (old implementation is `grp2idx()`)
set operations	UNION INTERSET	union() intersect() setdiff(), setxor()
sort	ORDER BY	sortrows()
unique	SELECT DISTINCT	unique()
reduction aggregration	F()	@reductionFunctions
grouping	GROUP BY	Specifying ‘GroupingVariables’ in varfun(), rowfun(), etc.
partitioning	(set partition option in Table Definition)	`T1=T(:, {'key', varnames_1})` `T2=T(:, {'key', varnames_2})`
joins	[type] JOIN	*`join(T1, T2, ...)`	df.join(df2, …)
cartesian product	CROSS JOIN (misnomer, no keys)	`T_cross = [repelem(T1, size(T2,1), 1), repmat(T2, [size(T1,1), 1])]`

Function programming concepts map (linear index), filter (logical index), reduce (summary & group) are heavily used with databases

Formal databases has a Table Definition (Column Properties) that must be specified ahead of time and can be updated in-place later on (think of it as static typing). Heterogenous Data Tables can figure most of that out on the fly depending on context (think of it as dynamic typing). This impacts:

data type (creation and conversion)
unspecified entries (NULL).
Often NaN in MATLAB native types but I extended it by overloading relevant data types with a isnull() function and consistently use the same interface
default values
keys (Indices)

SQL features not offered by heterogenous data tables yet:

column name aliases (AS)
wildcard over names (*)
pattern matching (LIKE)

SQL features that are unnatural with heterogeneous data tables’ syntax:

implicitly filter a table with conditions in another table sharing the same key.
It’s an implied join(T, T_cond)+filter operation in MATLAB. Often used with ANY, ALL, EXISTS

Fundamentally heterogenous data types expects working with snapshots that doesn’t update often. Therefore they do not offer active checking (callbacks) as in SQL:

Invariant constraints (CHECK, UNIQUE, NOT NULL, Foreign key).
Auto Increment
Virtual (dependent) tables (CREATE VIEW)

Know these database/spreadsheet concepts:

Tall vs wide tables

Language logistics (not related to database)

Concepts	SQL	MATLAB (table/dataset)	Pandas (Dataframe)
Partial display	MySQL: LIMIT Oracle: FETCH FIRST	`T( 1:10, : )`	`df.head()`
Comments	`--` or `/` … `/`	`%` or `%{` … `%}`	`#` or `"""` … `"""`
function	CREATE PROCEDURE fcn	`function [varargout{:}]=fcn(varargin{:})`	`def fcn:`
case	CASE WHEN THEN ELSE END	switch case end	(no case structure, use dictionary)
Null if no results	IFNULL ( statement )	`function X=null_if_empty(T, cond)` `X=T( cond, : );` `if( isempty(X) ) X=NaN;`
Replace nulls	ISNULL(col, target_val)	`T.col(isnan(T.col)) = target_val` `T = standardizeMissing( T, ... )`

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Rambling Nerd with a Plan

Hoi Wong's blog

Author Archives: admin

Reading Lambda Calculus

Using Dart’s C-style syntax to make chain of lambda functions concrete

Styles for (Lambda) anonymous function (named or unnamed) in Dart Language

MATLAB repeating arrays (elementwise array replication, interleaved ‘repmat’)

Data Relationships of Spreadsheets: Relational Database vs. Heterogenous Data Tables