DEV Community: Yufan Lou

Don't forget your --release flag when benchmarking

Yufan Lou — Mon, 04 Jan 2021 06:52:59 +0000

Saw this very old post comparing k-NN algorithm implemented in different languages, and for the love of my life I can't believe Rust runs the thing in over 1 minute.

So I took the code referred to in the post and ran it. Well it ran in over 40 seconds. I puzzled for an hour, even trying to implement the Go style code in Rust.

Then I realized I forgot the --release flag. I append it. It runs in not even a second.

How I got distracted by this when I was on that old blog for Hindley-Milner is another question.

Adventure Migrating to Apple Silicon

Yufan Lou — Sun, 29 Nov 2020 18:06:45 +0000

Setting up my Apple Silicon Macbook Pro. It is really snappy! and quiet!

I chose to jump on the new ship because I am very anxious about battery life and could barely disconnect the charger from my old Macbook Pro. With the new Macbook Pro I was compiling stuff and watching video and after three hours the battery shows 82%. That feels so reassuring.

Other than that, the biggest reason I am migrating away from my old Macbook Pro is its keyboard problems. I actually prefer the clicky feel and light actuation force I get on the Butterfly keyboard, but I have got several keys shadowing (type twice when pressed once) and my tab key is stuck. The Magic keyboard is heavier, very similar to my old Macbook Air.

I chose not to migrate my application folder, and decided to reconfigure my zsh environment so I moved my zshrc to a backup file.

I reinstalled IntelliJ IDEA and it runs nicely enough after translation by Rosetta 2. It feels on par with my Intel Macbook for what small projects I have. The menu highlight lags behind the cursor a bit. I will test it further in the coming days.

My homebrew installation is migrated and the Intel git from it worked. That confused me a bit at first. How seamless it feels. I still chooses to unlink it.

On the other hand, my Intel brew is prohibited by the devs from installing new programs while they figure out Apple Silicon support. So I set out to follow the community guide and installing a new homebrew at /opt/homebrew for Apple Silicon.

Parallel to that, to recover my Starship command line prompt I set out to install Rust. My Intel Rust toolchain is also migrated so when I ran the installation script from rustup it updated my Intel toolchain instead. I set up the PATH according to its instruction, and installed the Apple Silicon toolchain with rustup toolchain install beta-aarch64. I set it as default with rustup default beta-aarch64.

Trivia: the architecture of Apple Silicon is called ARM64, but the architecture in the Rust triplet is called AArch64. This difference is a historical artifact from Apple and ARM developing their 64-bit ARM architecture in parallel. Linux initially called this backend ARM64, and Apple did so in-house too, but ARM chose to call it AArch64 (and the 32-bit mode AArch32) when ARM released ARMv8-A. In LLVM, the two backends merged on 24 May 2014 into a new ARM64 backend.

cargo install starship gave me an error about wrong architecture regarding libgit2. I realized it was linking with the Intel libgit2 migrated over, originally installed by my Intel homebrew. I unlinked it and tried again. This time the error is about sysinfo. A pull request has fixed this issue but it is not released yet, so I use cargo install --git https://github.com/starship/starship.git instead, and it built successfully.

Now that starship is in command, I go back to the homebrew installation. I now have Intel brew at /usr/local/bin/brew and ARM brew at /opt/homebrew/bin/brew. I don't want to mess with my executables but I want to install ARM libraries so I can build against them. So I add /opt/homebrew/bin to PATH before /usr/local/bin. I use /usr/local/bin/brew bundle dump to dump the list of all installed packages to a Brewfile. I went into it and added # to every line to comment them out, and only removed it for lines with lib in it. Then I /opt/homebrew/bin/brew bundle to install from the file, and plugged the Macbook in and went to sleep.

With the relatively small number of libraries I have, I met three libraries failing to install: libbluray, libsoxr, and libgcrypt. libbluray is blocked on openjdk failing. libsoxr and libgcrypt are listed as working on the community guide, but I see the following error for libsoxr:

Undefined symbols for architecture arm64:
  "_av_get_cpu_flags", referenced from:
      _soxr_create in soxr.c.o
ld: symbol(s) not found for architecture arm64

and the following error for libgcrypt:

PASS: bench-slope
SKIP: hashtest-256g
======================================
1 of 27 tests failed
(1 test was not run)
Please report to http://bugs.gnupg.org
======================================

I later found Sam's great post to realized that I need arch -x86_64 prefix to install things with Intel homebrew. I will try this when chance presents.

How To Exit Press-To-Test on TI Nspire CX (CAS)

Yufan Lou — Wed, 14 Oct 2020 11:08:37 +0000

This how-to is a description of the solution in this video.

I don't remember clearly but I think I got this TI-Nspire CX CAS calculator as a gift from my library tutoring job. While I was tinkering with it I got it into the Press-To-Test mode. I thought the "test" means some system self-evaluation stuff, but turns out it means an exam at school or something like SAT. The mode heavily restricts the available features on the calculator as required by testing institutions.

To get out of it we need to use TI-Nspire Computer Link. TI provides installers for Windows and macOS.

Create an empty Note on the calculator, save it as "Exit Test Mode".
Install TI-Nspire Computer Link on the computer and open it.
Connect the mini-USB socket on the calculator to a USB socket on the computer.
Refresh the device list and choose the calculator.
Drag and drop the "Exit Test Mode" Note file to anywhere on the computer.
Drag and drop the "Exit Test Mode" Note file from the computer to the "Press-To-Test" folder.

If successful, we should see the "Press-To-Test" folder disappear, and Press-To-Test mode gone.

The Usefulness of GPT-3 Deserves The Virality

Yufan Lou — Wed, 12 Aug 2020 16:24:39 +0000

This is a comment on Agustin Lebron's The case against the import of GPT-3, as quoted by Tyler Cowen. I know nothing about the two, apart from stumbling upon it when I was looking for Max Woolf's Tempering Expectations for GPT-3 and OpenAI’s API.

Max Woolf's evaluation is very precise and valid, and with which I have to agree. The hype of GPT-3 on Twitter is obviously subject to selection bias. I'd even add survivorship bias on top, which virality always brings. And there are many details, from ethical to legal to economic, to iron out before a commercially successful product using GPT-3 can appear on the market. After all, technology is only one part of any business.

What I take issue with is Lebron taking Woolf's evaluation one step further, and writes that "we're not replacing front-end devs with attention-layer-stacks anytime soon." I take issue with the thinking that the effect of GPT-3 starts and ends with "replacing front-end devs".

I take issue with such thinking because of also survivorship bias, but in a different context: the most visible "replacing" happens to the existing surviving workers, while the loss of future workers are much less so.

To wit, the US has lost 15% of librarian jobs nationwide from 2009-10 to 2015-16, due to a demand for "digital learning specialists" instead. At the center of digital learning is the largest machine learning service deployed: Google.

There are ample research showing that Google cannot replace librarians entirely. That librarians perform many duties Google cannot. But nonetheless, Google is still replacing librarians in many senses of that word. We no longer need to ask a librarian which is the highest mountain peak of the world. We no longer need to ask a librarian for some nice recipes.

Librarians use Google, too. Librarians helped develop Google Scholar. However with Google Scholar, we need, or at least the school administrators think that we need, fewer librarians.

Seeing that GPT-3 is an even smarter model than the one behind Google, and that even Google has displaced librarians, it is inevitable that products based on GPT-3 will similarly displace workers somewhere, to some extent. "Replacing" a whole profession to extinction is indeed rare, as many traditional crafts are still preserved as cultural heritage without economic benefits. Replacing workers, though, is much easier.

A Merit of Learning a New Language

Yufan Lou — Tue, 28 Jul 2020 06:25:58 +0000

There are times when I find it hard to express my thinking in a certain way in the new language because I am not familiar enough with it, and I need to find an alternative way. That requires alternative thinking. Sometimes the alternative thinking can be quite a departure from the original, even changing my perspective, sometimes semantically, sometimes genuinely.

I just really couldn't find a good way to express "that's not what I meant" in Japanese. I resorted to "excuse me for making you misunderstand" instead.

Implementation vs Specification

Yufan Lou — Sat, 18 Jul 2020 22:22:42 +0000

Specification is like a macroeconomics model. It describes the general purpose and trend of the system.

Implementation is like a microeconomics model. It describes the operation and machinery of the system.

Three Vim Features

Yufan Lou — Sat, 18 Jul 2020 09:56:43 +0000

To split a line at pattern:

 :5s/pattern/<c-v><cr>/g

<c-v>, or Ctrl-v, in terminal waits for the next character, and inserts it as a literal (verbatim). So upon pressing <cr> (carriage return a.k.a enter key), instead of executing the command, the literal carriage return character (would be shown as ^M) is inserted at the cursor, which is then replaced into the file.

^M is the caret notation of carriage return. Other control characters can be similarly inserted with their corresponding key in the caret notation. For example, cancel is ^Z, so to insert it type

<c-v><c-z>

To copy the whole file into clipboard:

:%y+<cr>

To insert the content of a register, for example, clipboard:

<c-r>+

Sort in Linear Time, But Is It Worthy?

Yufan Lou — Tue, 14 Jul 2020 11:22:46 +0000

I know the fastest sorting algorithm is quicksort. It is even named accordingly. I also know that its time complexity is on average O(nlog(n)). Is there ever a sorting algorithm in linear time?

Yes, it turns out. It is called radix sort, and it actually predates modern computer.

What is radix sort? Radix sort is to sort numbers digit by digit. Or sort words letter by letter. It is so named because it uses a buffer of which the size becomes the radix of the sorted numbers. The radix is the number of possible digits in one position. Using a buffer of size 10, you can sort 0 to 9 in one iteration; using a buffer of 256 you can sort 0 to 255 in one iteration. The size is chosen according to memory limits, and in exchange sorting each additional digit takes another iteration.

Radix sort was THE algorithm used by IBM card sorters, which inherited the algorithm from tabulating machines.

How is radix sort linear? The number of iterations you go through the list to be sorted does not depend on the number of items, but the maximum number of digits or letters of the items, which is often a lot fewer than the number of items. If you know the maximum in advance, like if you know you are sorting 32-bit integers with a radix 2, then your time complexity is at most O(32n), which is indeed linear.

Linear time is categorized as being faster than n-logarithmic time. But in real world usages, the logarithmic term in n-logarithmic time is often smaller than the constant term in linear time. For the logarithmic term to reach 32, the number of items you are sorting needs to reach 2^32, which is 4 billion.

With a larger radix, like 256, the constant term of radix sorting for 32-bit integers becomes 4 (=32/log(256)), and to reach that with a logarithmic term the number of items necessary becomes 16. But even above 16 items, when is the improvement in sorting speed worth the additional 1 MB of memory (256 32-bit integers)?

All logarithmic above are base 2.

Apple Silicon Is Also A Chance To Improve Security

Yufan Lou — Thu, 09 Jul 2020 21:18:17 +0000

Toward trusted sensing for the cloud: Introducing Project Freta - Microsoft Research

The fact that sensor evasion is possible at all is surprising to many outsiders to the field of computer security. Anyone who’s visited a retail store understands that it’s a good idea to put the security cameras out of reach—why haven’t we done something similar in the cloud? The answer is a familiar one: backwards compatibility. Our first networked computers didn’t have the silicon real estate to devote to an isolated security sensor. Opportunities for technology companies to break backwards compatibility and “greenfield” redesign with security in mind have appeared only periodically, seen primarily in the mobile and console industries. These redesigns have allowed for increasing hardware separation between the compute plane and the security plane

Apple changing Macs to Apple silicon presents a similar opportunity to break backwards compatibility and redesign the security architecture. They kind of tried it with the T2 co-processor, but the complete transition may lead to a something more. How the isolation (lock-down) in macOS has been progressing up to Catalina might have also been in preparation for this, and Big Sur might be closer to iOS in more ways than the UI. I look forward to all the analyses that might come out from Objective-See.

I suppose some people get annoyed at the degree of lock-down Apple has been introducing. Personally, I've locked down my Linux instances even more. I just don't have the expertise and time to figure out how to lock it down without impairing the user experience too much, and I am glad Apple has been at it all this time.

Today I Learned Program and Coprogram

Yufan Lou — Thu, 09 Jul 2020 09:13:04 +0000

How to design co-programs | Patterns in Functional Programming

On the tail of the last random thought I realized data transformations are reinterpretations of constructors. That turns out to be a very established pattern in program design. Implicit in my thought was that constructors means constructors of the input. Like any established pattern, it has a dual. Enter coprogram, which are reinterpretations of constructors of the output.

The motivating example of zip is quite impressive. zip takes two lists and transform them into one list of pairs, pairing corresponding elements.

zip :: [a] -> [b] -> [(a,b)]

The conventional way of defining zip is case analysis on the input, as shown in the Haskell Prelude.

zip []     _bs    = []
zip _as    []     = []
zip (a:as) (b:bs) = (a,b) : zip as bs

What if we case analyze the output instead? Instead of asking "what is the output when input is empty", what if we ask "what is the input when output is empty"?

zip as bs = 
    if null as || null bs then []
    else (head x, head y) : zip (tail x) (tail y)

This concept adds a very welcome stepping stone between structural recursion and divide-and-conquer.

Today I Learned (Not) Reflection

Yufan Lou — Thu, 09 Jul 2020 06:32:11 +0000

An intuition for reflection | QA9

This reflection is not the one for metaprogramming, but the property that if you fold a piece of data with its constructors, you get back the piece of data itself. In terms of list in Haskell, with constructors:

[] :: [a]
(:) :: a -> [a] -> [a]

and a folding function like this:

foldr :: (a -> b -> b) -> b -> [a] -> b

The property of reflection is then defined as this equation:

foldr (:) [] = id

Another "Today I Learned" quote:

It is known (although I am not sure where you can find this in a paper) that if you have parametricity and reflection, you can derive induction.

Especially revelatory quotes:

With induction, we are trying to summarize an infinite number of cases in some finite way. This finite way is with the constructors for the datatype.

not taking constructors and datatypes for granted, we might ask: but how do you know you correctly summarized that infinite set of values using your functions you call constructors

My intuition about reflection is that it contributes an essential property towards knowing you have the correct summary of your infinite set of data.

A philosophical quote:

All it does is go through the list and interpret cons as cons, nil as nil.

Data transformation is all about reinterpreting the constructors of data.

(Ok) Tagless Final in Rust

Yufan Lou — Fri, 03 Jul 2020 08:50:51 +0000

Rust nightly has Higher-Kinded Type! 🔥

OMG I still don't know what use this has but damn it felt magical.

Props to whoever in the compiler team working on this.

You actually have to mark the output type correctly as L::Repr<bool>!

If you pass a L::int(1) to L::add it's a compile time error and the compiler tells you that i64 doesn't match bool!

Gosh. Awesome. Amazing.

Now let's hope this won't tank the compilation time too much. 😛

#![allow(dead_code)]
#![allow(non_snake_case)]
#![allow(incomplete_features)]

#![feature(generic_associated_types)]

/*
let b (bv:bool) env = bv
let int (iv:int) env = iv
let and b1 b2 env = b1 & b2
*/

type Func<T, O> = Box<dyn FnOnce(T) -> O>;

trait Lang {
    type Repr<T>;
    fn b(bv: bool) -> Self::Repr<bool>;
    fn int(iv: i64) -> Self::Repr<i64>;
    fn and(b1: Self::Repr<bool>, b2: Self::Repr<bool>) -> Self::Repr<bool>;
}

use core::marker::PhantomData;
struct B<P>(PhantomData<P>);
impl<P: 'static + Copy> Lang for B<P> {
    type Repr<T> = Func<P, T>;
    fn b(bv: bool) -> Self::Repr<bool> {
        Box::new(move |_env| bv)
    }
    fn int(iv: i64) -> Self::Repr<i64> {
        Box::new(move |_env| iv)
    }
    fn and(b1: Func<P, bool>, b2: Func<P, bool>) -> Func<P, bool> {
        Box::new(move |env| b1(env) & b2(env))
    }
}

struct P;
impl Lang for P {
    type Repr<T> = String;
    fn b(bv: bool) -> String {
        bv.to_string()
    }
    fn int(iv: i64) -> Self::Repr<i64> {
        iv.to_string()
    }
    fn and(b1: String, b2: String) -> String {
        format!("{} & {}", b1, b2)
    }
}

fn prog1<L>() -> L::Repr<bool>
where 
    L: Lang,
{
    L::and(L::b(false), L::b(true))
}

// fn prog_with_error<L>() -> L::Repr<bool>
// where
//     L: Lang,
// {
//     L::and(L::int(3), L::b(true))
// }

fn main() {
    let test1_p = prog1::<P>();
    println!("{:?}", test1_p);
    let test1_b = prog1::<B<()>>()(());
    println!("{:?}", test1_b);
}

// TODO: De Brujin Indices