Why Yg = g(Yg) Enables Recursion, 2

Posted on December 30, 2024 by rpflee

In essence, $Yg = g(Yg)$ allows for recursion by providing a mechanism where a function can reference itself through another function’s application, without needing to explicitly name itself, thus bypassing the need for direct recursion support in the language. This approach is particularly useful in theoretical computer science, lambda calculus, and in functional programming languages or environments where direct recursion might be restricted or not available.

— Based on Grok 2

— Edited by Me@2024-12-19 11:26:25 AM

Focused Connections

Posted on December 29, 2024 by rpflee

idea

~ 主意

~ a thought with a focus

~ connections, with a focus, of concepts

— Me@2015-10-20 08:45:36 AM

好為人師 3.2

Posted on December 28, 2024 by rpflee

這段改編自 2023 年 6 月 23 日的對話。

…… 原因是，雙方也會出於禮貌，即使在不同意對方時，也不會直斥其非、議事論事。既然不是開心見誠，無所顧忌，而是有所隱瞞，那就會導致誤會，日久累積加深。這情況在本人身上，發生不少次。有時是與學生反面，有時則是和教授，不相往來。

例子一：

我在大學做研究助理時，有次遇到一位舊生甲。他在中學時，我有教過他。我們在校內餐廳，傾談了一個小時多，十分投契。他鄉遇故知，格外開心。

不料，不久之後，甲跟他的舊同學，講了一些批評我的說話。批評本身不是問題。但是甲的批評方法，有兩大問題：

一、為何不當面提及？（因為我是師輩，當面批評，可能有失禮貌。）

當面提及的話，大家可以討論和爭拗，從而誤會最小化。

二、甲想像了一些從沒發生，甚至與實情相反的事件；又引述了一些，我從來未說過的話，或者我從來未有過的立場。當面提及的話，我可以當面釐清。又或者，我其實真的有失言，只是忘記了；他又可以立刻指正之。

我不介意被誤會，但介意因為被騙，誤以為對方想跟我聊天，而導致浪費了，一個小時多。

再後來，他邀請我參加他的婚宴時，我婉拒了，因為我不好意思去。我不知道，他真的想見我，還是客氣而已。

— Me@2024-12-28 07:02:54 PM

Euler problem 25.2.1

Posted on December 26, 2024 by rpflee

import System.CPUTime
import Text.Printf (printf)

-- | Times the execution of a pure function and prints the result.
time :: (Show a) => a -> IO a
time result = do
    start <- getCPUTime
    let computed = result
    end <- computed `seq` getCPUTime
    let diff = (fromIntegral (end - start)::Float)/(10^12)
    printf "Result: %s\n Time taken: %.6f seconds\n" (show computed) diff
    return computed

fibs :: [Integer]
fibs = 0:1:zipWith (+) fibs (tail fibs)

t :: Integer
t = 10^999
 
p25 :: Int
p25 = length w
    where
      w = takeWhile (< t) fibs

λ> time p25
Result: 4782
 Time taken: 0.000496 seconds
4782
λ>

λ> time p25
Result: 4782
 Time taken: 0.002918 seconds
4782
λ>

— Me@2024-12-25 07:00:13 AM

SageMath for Ubuntu 24.04

Posted on December 24, 2024 by rpflee

0. In this tutorial, you will need to go to the official website of NixOS. Make sure that its website is the real, official one. Any instructions from an imposter website can get your machine infected with malware.

1. Assuming your computer’s OS is Ubuntu 24.04 or above, go to the NixOS official website. Follow the instructions to install the Nix package manager (not the NixOS operating system) onto your OS. Choose the “single-user installation” method.

2. Run this command to install SageMath:

nix-env -iA nixpkgs.sage

3. Run this to open:

sage --notebook=jupyterlab

— Me@2024-11-27 12:28:48 AM

Y combinator

Posted on December 23, 2024 by rpflee

Why $Yg = g(Yg)$ Enables Recursion

The following calculation verifies that $Yg$ is indeed a fixed point of the function $g$ :

$\begin{aligned} Y g &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g \\ &= (\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)) \\ &= g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x))) \\ &= g\ (Y\ g) \end{aligned}$

The lambda term $g\ (Y\ g)$ may not, in general, $\beta$ -reduce to the term $Y\ g$ . However, both terms $\beta$ -reduce to the same term, as shown.

— Wikipedia on Fixed-point combinator

$\begin{aligned} Y g &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g \\ &= (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ (f := g) \\ &= (\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)) \\ &= (\lambda x.g\ (x\ x))\ (\lambda y.g\ (y\ y)) \\ &= (\lambda x.g\ (x\ x))\ (x := (\lambda y.g\ (y\ y))) \\ &= g\ ((\lambda y.g\ (y\ y))\ (\lambda y.g\ (y\ y))) \\ &= g\ (Y\ g) \end{aligned}$

— Me@2024-12-22 11:53:21 PM

加了熱，動能也可以減

Posted on December 21, 2024 by rpflee

90-CE-PHY II – 18 前傳 2

— Me@2024-12-21 11:41:50 AM

真話騙子 2

Posted on December 20, 2024 by rpflee

這段改編自 2021 年 12 月 17 日的對話。

有誠信的人，會盡量不講假話；但是要留意，「誠信」並不只是，「講不講真話」的問題，因為，如果有心傷害人，只講真話也可以做到。

大方向是：

1. 不要在毋須講假話時，講假話。

2. 不要公開一些，毋須公開的真話。這就是「個人私隱」的意思。只有公職事務，你才有責任公開。

這兩點可統一為：

0. 不要在毋須說話時說話。

現在集中討論第一點：

即使是所謂的「善意」假話或隱瞞，也應盡量避免，因為結果為何，不是你，或者任何人，可以控制到。

……

— Me@2024-12-20 12:01:28 PM

Euler problem 25.1.2

Posted on December 16, 2024 by rpflee

(defun matrix-multiply (a b)
  (destructuring-bind ((a11 a12) (a21 a22)) a
    (destructuring-bind ((b11 b12) (b21 b22)) b
      (list (list (+ (* a11 b11) (* a12 b21))
                  (+ (* a11 b12) (* a12 b22)))
            (list (+ (* a21 b11) (* a22 b21))
                  (+ (* a21 b12) (* a22 b22)))))))

(defun matrix-power (m n)
  (declare (type fixnum n))
  (cond ((= n 1) m)
        (t (let* ((half (matrix-power m (floor n 2)))
                  (squared (matrix-multiply half half)))
             (if (oddp n)
                 (matrix-multiply squared m)
                 squared)))))

(defun digits-in-number (n)
  "Count the number of digits in a number."
  (length (write-to-string n)))

(defun fib-nth (n)
  (declare (type fixnum n))
  (if (<= n 2)
      1
      (destructuring-bind ((result b)
                           (c d))
          (matrix-power '((1 1) (1 0)) (- n 1))
        (declare (ignore b c d))
        result)))

(defun fib-upper-bound (digit-count)
  "Calculate an upper bound for the index where Fibonacci has at least digit-count digits."
  (let* ((phi (float 1.618033988749895))
         (log-phi (log phi 10))
         (log-5 (log 5 10)))
    (ceiling (/ (+ digit-count (- 1 (/ log-5 2))) log-phi))))

(defun binary-search-fib-index (digit-count)
  "Find the index of the first Fibonacci number with the specified number of digits using binary search."
  (labels ((binary-search (left right)
             (when (<= left right)
               (let* ((mid (+ left (floor
                                    (/ (- right left) 2))))
                      (mid-fib (fib-nth mid))
                      (mid-digits (digits-in-number mid-fib)))
                 (cond ((= mid-digits digit-count) 
                        (let* ((prev-fib (fib-nth (1- mid)))
                               (prev-digits (digits-in-number
                                             prev-fib)))
                          (if (< prev-digits digit-count)
                              mid
                              (binary-search left (1- mid)))))
                       ((< mid-digits digit-count) 
                        (binary-search (1+ mid) right))
                       (t 
                        (binary-search left (1- mid))))))))
    (let* ((upper-bound (fib-upper-bound digit-count))
           (result (binary-search 1 upper-bound)))
      (or result (cons :upper-bound upper-bound)))))

; SLIME 2.28
CL-USER> (time (binary-search-fib-index 1000))
Evaluation took:
  0.001 seconds of real time
  
4782
CL-USER>

— Me@2024-12-10 07:23:47 PM

Ex 3.3: Hill Climbing, 2

Posted on December 15, 2024 by rpflee

Functional Differential Geometry

b. Write this as a computational expression.

~~~

…

$\begin{aligned} P &= mg \frac{d h}{d t} \\ &= mg \left( \frac{\partial h}{\partial x} \frac{dx}{dt} + \frac{\partial h}{\partial y} \frac{dy}{dt} \right) \\ &= mg \begin{bmatrix} \frac{\partial h}{\partial x} & \frac{\partial h}{\partial y} \end{bmatrix} \begin{bmatrix} \frac{dx}{dt} \\ \frac{dy}{dt} \end{bmatrix} \\ &= mg (\nabla h) \cdot \mathbf{v} \\ &= mg (D f(\chi(\mathbf{m})) b(\chi{(\mathbf{m}})) \\ \end{aligned}$

(define (components->vector-field components coordsys)
  (define (v f)
    (compose (* (D (compose f (point coordsys)))
                components)
             (chart coordsys)))
  (procedure->vector-field v))

(define R2->R (-> (UP Real Real) Real))

(define v
  (components->vector-field
   (up (literal-function 'v_x R2->R)
       (literal-function 'v_y R2->R))
   R2-rect))

(define R2-rect-chi-inverse
  (point R2-rect))

(define R2-rect-point
  (R2-rect-chi-inverse (up 'x_0 'y_0)))

(show-expression
 ((v (literal-manifold-function
      'h R2-rect)) R2-rect-point))

$\left( \left(v_x \left(\begin{pmatrix} x_0 \\ y_0 \end{pmatrix}\right) \cdot \left(\partial_0 h \right)\right|_{\begin{pmatrix} x_0 \\ y_0 \end{pmatrix}} + \left(v_y \left(\begin{pmatrix} x_0 \\ y_0 \end{pmatrix}\right) \cdot \left(\partial_1 h \right) \right|_{\begin{pmatrix} x_0 \\ y_0 \end{pmatrix}} \right)$

— Me@2024-11-22 04:05:26 PM

Equality Predicates, 3.1

Posted on December 14, 2024 by rpflee

Here are mnemonic “formulae” to help remember the relationship between eq, eql, equal, equalp, and = in Common Lisp:

eq:
```
eq: Exact same object in memory
```
Think “Exact” for eq.

eql:

eql: eq + little more (for numbers and characters)

Think “Little more” for eql.

equal:
```
equal: eql + structural comparison for lists, strings, etc.
```
Think “All” for equal – checks all structural elements.
equalp:
```
equalp: equal + case-insensitive + number type agnostic
```
Think “P for Practical” – it’s practical because it ignores case and number types.
=:
```
=: Numbers are equal regardless of type (float vs. integer)
```
Think “= for Numbers” – only used for numeric comparison.

These mnemonics aim to encapsulate the essence of each function:

eq is about memory identity.
eql extends eq slightly for direct value comparison in some cases.
equal checks for structural equivalence beyond what eql does.
equalp adds case insensitivity and type flexibility to equal.
= is strictly for numeric equality, ignoring type differences.

— Me@2024-12-14 10:57:53 AM

Mind City 3

Posted on December 13, 2024 by rpflee

Within the physical laws, you can command your MIND to control your health.

— Me@2009.03.12

Your mind can control any software, but only some hardware.

— Me@2009.03.13

— Me@2024.12.13

Where are you? 2.6

Posted on December 12, 2024 by rpflee

Utopia | 何有之鄉, 2.6

不可能遷就到，而為了保命，必須立刻超光速逃離，或者𣊬間轉移的例子有：

……

五、不可信：

……

這類人不可相處之的主要原因是，他們認為，謊言只要不被發現，就沒有問題。他們覺得，既然受騙者不知道，就不會不開心，不會受傷害。所以，即使騙了他人，那也不算不道德。

這種講法，有兩漏洞。

小漏洞是，你怎麼肯定，你的謊言不會爆煲？

大漏洞是，要永久不被發現，你的心神就要，永久經營那些大話，心情永久不能放鬆。

記住，維持誠信有如保持健康，主要是為了自己而做的；他人知不知道，沒有關係。

以下是例外情形，可能有必要講假話。

……

其他情形下，謊言假話，幾乎一概不可接受。

……

— Me@2024-09-05 03:33:08 PM

Euler problem 25.1.1

Posted on December 11, 2024 by rpflee

(defun fib (n)
  "Calculate the nth Fibonacci number using tail recursion."
  (labels ((fib-tail (a b count)
             (if (zerop count)
                 b
                 (fib-tail b (+ a b) (1- count)))))
    (if (<= n 2)
        1
        (fib-tail 1 1 (- n 2)))))

(defun matrix-multiply (a b)
  (destructuring-bind ((a11 a12) (a21 a22)) a
    (destructuring-bind ((b11 b12) (b21 b22)) b
      (list (list (+ (* a11 b11) (* a12 b21))
                  (+ (* a11 b12) (* a12 b22)))
            (list (+ (* a21 b11) (* a22 b21))
                  (+ (* a21 b12) (* a22 b22)))))))

(defun matrix-power (m n)
  (declare (type fixnum n))
  (cond ((= n 1) m)
        (t (let* ((half (matrix-power m (floor n 2)))
                  (squared (matrix-multiply half half)))
             (if (oddp n)
                 (matrix-multiply squared m)
                 squared)))))

(defun fib-nth (n)
  (declare (type fixnum n))
  (if (<= n 2)
      1
      (destructuring-bind ((result b) (c d))
          (matrix-power '((1 1) (1 0)) (- n 1))
        (declare (ignore b c d))
        result)))

(defun digits-in-number (n)
  "Count the number of digits in a number."
  (length (write-to-string n)))

(defun find-fib-index-0 (digit-count fib-f)
  "Find the index of the first Fibonacci number with the specified number of digits."
  (labels ((helper (index)
             (if (>= (digits-in-number
                      (funcall fib-f index))
                     digit-count)
                 index
                 (helper (1+ index)))))
    (helper 1)))

(defmacro find-fib-index (digit-count)
  `(find-fib-index-0 ,digit-count #'fib))
  
(defmacro find-fib-nth-index (digit-count)
  `(find-fib-index-0 ,digit-count #'fib-nth))

; SLIME 2.28
CL-USER> (time (find-fib-index 1000))
Evaluation took:
  0.456 seconds of real time
  
4782
CL-USER> (time (find-fib-nth-index 1000))
Evaluation took:
  0.080 seconds of real time
  
4782
CL-USER> (time (binary-search-fib-index 1000))
Evaluation took:
  0.001 seconds of real time
  
4782
CL-USER>

— Me@2024-12-10 07:23:47 PM

Ex 3.3: Hill Climbing, a

Posted on December 10, 2024 by rpflee

Functional Differential Geometry

The topography of a region on the Earth can be specified by a manifold function $h$ that gives the altitude at each point on the manifold. Let $v$ be a vector field on the manifold, perhaps specifying a direction and rate of walking at every point on the manifold.

a. Form an expression that gives the power that must be expended to
follow the vector field at each point.

b. …

~~~

Let $f$ be a real-valued function, $\mathbf{m}$ be a point, $\mathbf{v}$ be a vector field on the manifold function respectively:

$\begin{aligned} h \left( \begin{bmatrix} x \\ y \end{bmatrix} \right) &= f\left(\chi (\mathbf{m}) \right) \\ \mathbf{v} &= \frac{d}{dt} \begin{bmatrix} x \\ y \end{bmatrix} \\ \end{aligned}$

…

— Me@2024-11-22 04:05:26 PM

defmacro, 1.2.1

Posted on December 9, 2024 by rpflee

(defmacro our-expander (name) `(get ,name 'expander))
 
(defmacro pre-defmacro (name parms &body body)
  (let ((g (gensym)))
    `(progn
       (setf (our-expander ',name)
         #'(lambda (,g)
         (block ,name
           (destructuring-bind ,parms (cdr ,g)
             ,@body))))
       ',name)))
 
(defun our-macroexpand-1 (expr)
  (if (and (consp expr) (our-expander (car expr)))
      (funcall (our-expander (car expr)) expr)
      expr))

(defun our-macroexpand (expr)
  (let ((expanded (our-macroexpand-1 expr)))
    (if (equal expanded expr)
        expr
        (our-macroexpand expanded))))

(defun our-macroexpand-and-eval (expr)
  (if (and (consp expr) (our-expander (car expr)))
      (let ((expanded (funcall (our-expander (car expr)) expr)))
        (eval expanded))  ; Directly evaluate the expanded form
      (eval expr)))  ; If no macro expansion, just evaluate the expression

(defmacro our-defmacro (name parms &body body)
  `(progn
     (pre-defmacro ,name ,parms ,@body)
     (defun ,name (&rest args)
       (our-macroexpand-and-eval (cons ',name args)))))

(our-defmacro sq (x)
  `(* ,x ,x))

(sq 5)

— based on p.95, A MODEL OF MACROS, On Lisp, Paul Graham

— xAI

Here, we use the built-in defmacro to define our-defmacro. However, the same process does not work for another level of defining another-defmacro by our-defmacro, because our-defmacro is not identical to defmacro.

— Me@2024-12-09 01:40:02 PM

反情感勒索, 3

Posted on December 6, 2024 by rpflee

「報恩」反邏輯。要「報」就不叫做「恩」。需要報的，必須報的，就不是「恩」，是「交易」。

有沒有往來，在於感情或喜歡，不在於恩。有情的，沒有恩也會對她好。

相反，傷害你的，即使是所謂的「恩人」，你也必須激烈反抗。

— Me@2024-11-28 10:23:47 AM

好為人師 3.1

Posted on December 6, 2024 by rpflee

這段改編自 2023 年 6 月 23 日的對話。

「平等關係」的意思是，雙方可以講真話之餘，在有需要時，可以講事實的全部真相，而毋須遮遮掩掩，避重就輕。

（留意，這裡並不是指，那些無腦式坦白。詳見本博文章「真話騙子」。）

教師和學生，並不是平等關係。那就可以導致，最終反目。原因是，雙方也會出於禮貌，即使在不同意對方時，也不會直斥其非、議事論事。既然不是開心見誠，無所顧忌，而是有所隱瞞，那就會導致誤會，日久累積加深。這情況在本人身上，發生不少次。有時是與學生反面，有時則是和教授，不相往來。

例子一：

……

— Me@2024-12-05 12:49:02 AM

Euler problem 24.3

Posted on December 4, 2024 by rpflee

showtime : true;

digits: makelist(i,i,0,9);

p : permutations(digits)$

listify(p)[1000000];

Evaluation took 0.8800 seconds (1.0300 elapsed)
Evaluation took 0.0100 seconds (0.0100 elapsed)

[2,7,8,3,9,1,5,4,6,0]

— Me@2024-12-03 04:11:50 PM

scmutils for Ubuntu 24.04

Posted on December 1, 2024 by rpflee

Scheme Mechanics Installation for GNU/Linux | scmutils, 4

1. Folks, the scmutils library is fantastic and it’s available in Ubuntu 24.04. You can install it very easily with this command:

sudo apt-get install scmutils

2. Then, you just run it with this command:

mit-scheme --band mechanics.com

Now, let me tell you, there’s no syntax highlighting. Not great! And more importantly, there’s no direct way to save your code. So, what do you do? You use the Emacs editor. It’s the best!

Now, this assumes you know Emacs. If you don’t, it’s a tremendous editor.

3. Open Emacs’ initialization file. It’s located right here:

~/.emacs

4. Add this beautiful code to the file:

(defun mechanics ()
  (interactive)
  (run-scheme
   "mit-scheme --band mechanics.com"))

(setq sicm-file "~/Documents/tt.scm")

(fset 'set-working-file
      (lambda (&optional arg) 
        (interactive "p")
        (funcall (lambda ()
                   (insert
                    (concat "(define sicm-file \""
                            sicm-file
                            "\")\n"))))))

(fset 'load-scm
      (lambda (&optional arg) 
        (interactive "p")
        (funcall (lambda ()
                   (insert "(load sicm-file)")))))

(defun mechan ()
  (interactive)
  (split-window-below)
  (windmove-down)
  (mechanics)
  (set-working-file)
  (comint-send-input)
  (windmove-up)
  (find-file sicm-file)
  (end-of-buffer)
  (windmove-down)
  (cond ((file-exists-p sicm-file)
         (interactive)
         (load-scm)
         (comint-send-input)))
  (windmove-up))

(defun sicm-exec-line ()
  (interactive)
  (save-buffer)
  (windmove-down)
  (comint-send-input)
  (windmove-up))

(defun sicm-exec-file ()
  (interactive)
  (save-buffer)
  (windmove-down)
  (load-scm)
  (comint-send-input)
  (windmove-up))

(global-set-key (kbd "C-x C-e") 'sicm-exec-line)

(global-set-key (kbd "C-x C-a") 'sicm-exec-file)

5. Close Emacs and then re-open it, folks.

6. Type the command

M-x mechan

Now, listen, when I say M-x, I mean you press the Alt key and x together. Then, just type mechan. It’s easy, believe me!

7. You’ll see the Emacs editor split into two windows, one on top and one on the bottom.

The lower window is the Scheme environment. You can type a line of code and then press Enter to execute it. So simple!

The upper window is the editor. Type multiple lines of code and then hit

C-x C-e

to execute it.

That means pressing Ctrl and x together, then Ctrl and e together. Easy stuff!

8. When you save the current file, your Scheme code will be saved to this location:

~/Documents/tt.scm

If you need to back up your code, just back up this file. It’s that simple, folks!

— Me@2020-03-10 10:59:45 PM

Physics Town

continues

Monthly Archives: December 2024