A Chinese chess program with TypeScript type operations:
When TypeScript is a type system, it implements chess. I clone the TypeScript code and run it locally, in quotes, because TS is a dynamically derived type. Hover on the mouse can see the result.
Seeing this magic, I looked it up myself.
Turing complete
This is the first concept I came across, and Wikipedia defines it like this:
A computing system that can compute any Turing-computable function is called Turing complete (or Turing complete). Or any system that can simulate a universal Turing machine.
Computable functions are roughly understood as “problems that people can calculate”. However, nowadays, almost all programming languages, such as C++ and JAVA, have Turing completeness, which is a bigger problem. A more popular explanation can be seen as what is Turing completeness? Brainfuck is an interesting programming language invented by Urban Muller in 1993. Let’s see how it prints Hello World.
+++++ +++++ initialize counter (cell #0) to 10
[ use loop to set 70/100/30/10
> +++++ ++ add 7 to cell #1
> +++++ +++++ add 10 to cell #2
> +++ add 3 to cell #3
> + add 1 to cell #4
<<<< - decrement counter (cell #0)
]
> ++ . print 'H'
> + . print 'e'
+++++ ++ . print 'l'
. print 'l'
+++ . print 'o'
> ++ . print ' '
<< +++++ +++++ +++++ . print 'W'
> . print 'o'
Copy the codeYes, you read that correctly. Here is the code on the left and the comment on the right. Here is a single sentence execution diagram to get a feel for it:
The tape on top represents what’s going on in memory, and by moving it left, right, plus, minus, and minus, it says Hello World! .
TypeScript’s Turing completeness is also discussed in the TypeScript repository’s Issues, and the author shares an interesting code for determining whether or not it is prime.
Knowledge of TypeScript
In order to implement the title of this article, “Implementing the Fibonacci Sequence in TypeScript”, you need to learn about this topic.
The generic
If you have studied C++ or Java before, you are familiar with generics. Generics allow you to define function parameters without specifying the type of the parameter, instead using a placeholder.
For a simple example, implementing the addition of two elements requires writing the same logic multiple times with TypeScript constraints.
function addTwoNumber(a: number, b: number) :number {
return a + b;
}
function addTwoNumberString(a: string, b: string) :string {
return a + b;
}
addTwoNumber(1.3)
addTwoNumberString('1'.'2');
Copy the codeOtherwise, anyScript is the only option, with no type verification at all.
function addTwoNumber(a: any, b: any) :any {
return a + b;
}
addTwoNumber(1.3)
addTwoNumber('1'.'2');
addTwoNumber('1'.2); / / is not an error
Copy the codeIf you have generics, you can reuse logic and validate types.
function addTwoNumber<T> (a: T, b: T) :T {
return <any>a + <any>b; Operator '+' cannot be applied to types 'T' and 'T'. Ts (2365)
}
addTwoNumber(1.3);
addTwoNumber("1"."3");
addTwoNumber('1'.2); / / an error
Copy the codeOf course, there is a suspicion of forcing generics, but it is good to understand the general function of generics, haha. In the above case it would be better to use the TS overload.
Type the type
Number [], number[], ABC [], ABC [], ABC [], ABC [], ABC [] 1 is of type 1, which is also of number.
The most important thing is that TS allows us to define new types, and we can also, through generic variables, perform type operations and generate new types. A few examples:
type Type1<T> = T extends number ? number : string;
type Type2 = Type1<2121>; // Type2 equals number
type Type3 = Type1<{}>; // Type3 is equivalent to string
Copy the codeExstends and the rest? Form a ternary expression that is judged to be true if the type before extends can be assigned to the type after extends, and false otherwise.
Since a single number is also a type, we can determine if the T passed in is equal to something.
type Type4<T> = T extends 1 ? true : false;
type Type5 = Type4<2121>; // In this case Type5 is equivalent to false
type Type6 = Type4<1>; // In this case Type6 equals true
Copy the codeAnd you can kind of think about this a little bit, and it’s really important, because if you’re going to write the Fibonacci sequence, you’re going to get caught up in it, because you’re manipulating between types, and it’s very different than programming.
In short, each type can be viewed as a function, passing in a generic as a function parameter and a type, and finally returning a new type.
Type(type, type) => type
Copy the codeinfer
Infer represents the type variables to be inferred in the extends condition statement.
Infer R is the actual parameter type of the current type. Infer R is the actual parameter type of the current type when the type is inferred. Here’s an example:
We can determine whether T is the type of {a: XXX, b: XXX}. Since T is a generic type, we do not know what type of a in T is. When you pass in the specific type, you can figure out what type A is.
type Foo<T> = T extends { a: infer U; b: infer U } ? U : never;
type T1 = Foo<{ a: string; b: string }>; // THE T1 type is string
type T2 = Foo<{ a: string; b: number }>; / / T2 type string | number
Copy the codeFibonacci numbers
Fibonacci sequence is not explained, first with JS to achieve a Fibonacci sequence.
function Fibonacci(n) {
if (n === 1) {
return 1;
}
if (n === 2) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Copy the codeDon’t worry about the most important recursion, TS supports the recursive definition of the type, let’s write a rough prototype, it is interesting to see chess directly define the type in Chinese, here also directly Chinese. Each type can be thought of as a function. The generic passed in as a function parameter is also a type, and a new type is returned.
We define the Fibonacci type first. The generic type is passing in a number (the number is treated as a type), checking whether the type passed is 1 or 2, and then returning type 1 directly.
Type Fibonacci < a numberextendsNumber > = a numberextends 1
? 1: a number ofextends 2
? 1: add < Fibonacci < subtract one < some number >>, Fibonacci < subtract one < some number >>>>;Copy the codeIt is important to note that the extends in <> defines the type passed in, unlike the extends outside.
We also need to define a “add” type and a “subtract one” type.
Addition is the addition of two types, but the type system does not support the direct addition of numbers, 1 + 2 cannot be added directly, there is a trick here.
Array types have the same length attribute as arrays in JS, which returns a specific number type and supports extension operators. Here’s an example:
type A = [any, any, any]
type B = A["length"] // B is type 3
Copy the codeSo we can convert a number to an array, manipulate an array, and then convert an array back to a number through length.
I’m going to write a Type that gets the array, and that’s where the recursion comes in.
Type gets the length < arrayextendsAny []> = array ["length"]; Type is converted to an array < some numberextendsNumber, corresponding to the arrayextends any[] = [] // The default value is an empty array. External calls do not need to be passed> = Get length < array >extendsA number of// Whether the length is equal to the required length? Corresponding to the array// Return if the length is equal to the required length: converts to array < some number, [any,... array]>;// Otherwise add another element to the array and call recursively
Copy the codeWith a Type converted to an array, the addition method is easy to write. We simply convert the two numbers to the corresponding array, concatenate the two arrays, and return the concatenated array length.
typeAdd < a number aextends numberAnd a certain number of bextends number> = get the length < [... to array < a >,... to array < b >] >;Copy the codeAnd then we define the method of subtracting by one, which is the length of the array minus one. And we use infer here, and we also use the deconstruction of arrays.
Type Array minus one < an array typeextends any[]> = ((. Parameter: an array type) = > any) extendsBreak down a element: any... Infer The rest of array type) => any? The remaining array types are: [];Copy the codeWe define a function type that removes one element from the rest of the array by destructing the function arguments.
With the array subtracting one type, the number subtracting one comes naturally. Convert the number to the corresponding array, subtract one element from the array, and then revert to the number.
Type minus one < a certain numberextendsNumber > = get length < array minus one < convert to array < some number> >>;Copy the codeThe overall code comes out:
Type Fibonacci < a numberextendsNumber > = a numberextends 1
? 1: a number ofextends 2
? 1: add < Fibonacci < subtract one < some number >>, Fibonacci < subtract one < some number >>>>; Type gets the length < arrayextendsAny []> = array ["length"]; Type is converted to an array < some numberextendsNumber, corresponding to the arrayextendsAny [] = [] > = get length < array >extendsA number? Array: converts to array < some number, [any,... array]>; Type adds < a number aextendsNumber, a number of bextendsNumber > = get length < [... to array < a >,... to array < b >] >; Type Array minus one < an array typeextends any[]> = ((. Parameter: an array type) = > any) extendsBreak down a element: any... Infer The rest of array type) => any? The remaining array types are: []; Type minus one < a certain numberextendsNumber > = get length < array minus one < convert to array < some number> >>;/ / testFibonacci 8 = Fibonacci <8>
Copy the codeTake a look at the results:
But Fibonacci 11 is just too much recursion.
This is mainly to experience the Turing completeness of TS, not optimization.
conclusion
I learned more about the types of TS by writing this example, but I would never do this in normal development, mainly to write haha, after all, a simple Fibonacci sequence is such a trouble to write, quoting the title of Linus Torvalds’ autobiography, Just for Fun!