datalog

ผมแทบจะไม่สนใจ Prolog เลย แต่ว่าเป็น TA วิชา knowledge representation ก็เลยต้องมาอ่าน แล้วก็พบว่ามี Datalog ด้วยซึ่งเป็น subset ของ Prolog อีกที [1] อันนี้ที่อ้างไปเขาไปอ้างงานปี 1982 ีอกทีผมยังหาอ่านไม่ได้

datalog ก็เอามาใช้ในงาน query ต่าง ๆ คล้าย SQL นี่เอง, datalog เป็นของเก่าแต่กลายเป็นว่ากลับมานิยมในยุคนี้ เก่ากว่า SQL; Clojure นี่ Datatomic ก็ใช้ datalog ด้วยแต่ว่าก็ปรับ syntax ให้กลายเป็น Clojure แบบเนียน ๆ

datalog แน่นอนว่าเขียนแบบ logic แล้วก็ recursive ได้[2] [4] เขาเอามา define path จาก edge แบบ recursive ก็ดูสวยงามดี สั้นด้วย


Path(t, d) :- Edge(1, t, d).
Path(t, d) :- Path(s, d1), Edge(s, t, d2), d=d1+d2


แต่ผมไม่แน่ใจว่าถ้า recursive ไม่ได้ออกมาเป็นแบบไหน

อีกประเด็นหนึ่งที่อ่านเจอคือ complexity ของ SQL query evalulate เป็น NP-complete [5] ส่วนของ Ground positive Datalog เป็น PTIME-complete ซึ่งผมก็ยังงง ๆ ว่า ground positive คืออะไร ptime นี่คือ space ไม่ P หรือเปล่า ?

อีกเป็นที่เจอใน Wikipedia[6] คือ datalog ไม่มี cut แบบใน Prolog เพราะรับประกันได้ว่าโปรแกรม query จะหยุดถ้า query บน finite set ทำให้ Datalog นี้เป็น declarative ยิ่งกว่า Prolog อีก

ผมว่า Datalog มันน่าสนใจว่า Prolog ที่เรียน ๆ ไปนอกจากจะยังไม่ตายแล้วแล้วมันก็คึกคักในวงการวิจัยมาหลายปี ดู ๆ แล้วในภาควิสาหกิจ (Enterprise) ก็จะเริ่มเอาไปใช้แล้วด้วย

ป.ล. ถึงผมจะไม่ค่อยรู้เรื่องก็ตาม SQL:1999 ก็ recursive ได้ [3] แต่เขียนใส่ MySQL แล้วผมก็ไม่แน่ใจว่ามันจะได้หรือเปล่า (ยังไม่ได้ลอง)

[1] https://pdfs.semanticscholar.org/6304/44d76e5aa81867344cb11aaddaab8dc8174c.pdf
[2] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5470845/
[3] http://www.seas.upenn.edu/~cse400/CSE400_2006_2007/GuptaSyrotkin/writeup.pdf
[4] https://suif.stanford.edu/~courses/cs243/lectures/l12-socialite.pdf
[5] http://www.dis.uniroma1.it/~rosati/krst/comparison.pdf
[6] https://en.wikipedia.org/w/index.php?title=Datalog&oldid=799521469

Advertisements

ตัดคำ

รอบอก

concurrency ใน Crystal-lang

อ่านแล้วคิดว่า concurrency ใน Crystal-lang น่าจะดีพอ ๆ กับ Golang

หรือจะเรียกว่าทำตาม Golang เลยก็ได้ ?

code ที่ใช้ switch fiber นี่อัด assembly กันเลย

https://crystal-lang.org/docs/guides/concurrency.html

https://github.com/crystal-lang/crystal/blob/c26fbc9714c700d65190e89bf48f2743bb0122d0/src/fiber.cr

STM

อ่านคู่มือของ Clojure แล้วไม่ค่อยเจอเรื่อง mutex lock แต่ไปเจอ STM (Software Transactional Memory) แทน

พอเข้าไปดูเรื่อง STM ใน Wikipedia  เป็นเรื่องที่เผยแพร่ครั้งแรกโดย Tom Knight ตั้งแต่ค.ศ. 1986 เป็น concurrent control ที่พยายามจะทำให้คล้าย ๆ database transaction แทนที่จะมาใช้ mutex lock แล้วก็พบอีกว่า STM ใช้ได้กับหลายภาษาเลย เพราะทำในระดับ library เอา

พอไปหาต่อใน GitHub  ก็พบว่ามี lib สำหรับทำ STM ใน Rust ด้วย https://github.com/Marthog/rust-stm เข้าไปอ่านดูก็ประมาณว่าพยายามลอกแบบ Haskell มาอีกที แล้วเอา atomic operation มารวม ๆ กันเป็น atomic operation ใหม่ได้ด้วยซึ่งทำตามของ MSR ในปี 2005 (Harris, Tim, et al. “Composable memory transactions.” Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming. ACM, 2005.) อ่านเพิ่มได้จาก https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf

ข้างล่างนี้เป็นตัวอย่างที่ลอกจาก rust-stm มาดัดแปลง comment เอา แน่นอนว่าคงมั่ว ๆ โปรดชี้แนะด้วย

use stm::{atomically, TVar};

// เป็นตัวแปรที่จะ share กันระหว่าง thread
let var = TVar::new(0);

// ใน atomically นี้ผมเข้าใจว่ามันก็คล้าย ๆ begin ... commit ของ SQL 
// ประกันได้ว่า code ในนี้จะไม่ถูกหลาย ๆ thread มาเขียนอ่านสลับกันไปมาสนเสียลำดับ
let x = atomically(|trans| {
    var.write(trans, 42)?; // การใส่ ? คือถ้าเขียนไม่ได้ก็ คือ error ออกไปเลย
    var.read(trans) // พวก var.write var.read นี่น่าจะเป็น atomic operation ที่ว่าเอามารวมกันแบบในงานของ MSR
});

println!("var = {}", x);

เขียนประมาณนี้ก็จะทำให้มั่นใจได้ว่า var.read(trans) ไปอ่านค่า var.write(trans, 42) จาก thread เดียวกันมา ไม่ใช่ไปอ่าน var.write(trans, 42) ของ thread อื่น แต่ว่าตัวอย่างนี้มันคงง่ายไป เพราะว่ายังไงก็ write 42 อยู่แล้วจะ thread ไหนก็คงไม่ต่างกัน

ใน rust-stm วันที่ผมอ่านวันนี้ ข้างในเขาใช้ mutex lock กับ ARC เอาครับมี AtomicUsize ด้วย ที่เห็นคร่าว ๆ คือแค่ละ transaction จะมี BTreeMap เอาไว้เก็บ log ของแต่ละ var: TVar แต่ละตัว เวลาอ่านเขียนอะไรนี่ก็จะไปใส่ log ทั้ง value และบอกด้วยว่าเป็น Read Write ฯลฯ แล้วค่อยไป lock/release เอาตอน commit

แลมันก็น่าจะใช้ง่ายกว่า lock อย่างน้อย ๆ ก็บางกรณี นอกจากนั้นแต่ละ transaction มันก็ทำงานไปก่อนได้เลยโดยเขียนไปใน log โดยที่ไม่ต้องมารอ lock ใน rust-stm ก็มารอกันทีเดียวใน commit เลย แต่ว่าในเอกสารของ Clojure ก็บอกทำนองว่าจะใช้แบบ lock lock-free หรือ hybrid มา implement ก็ยังเป็นประเด็นในงานวิจัยอยู่

พยายามใช้ cpu ให้ครบทุก core

ผมไม่ค่อยรู้เรื่อง parallel computing เท่าไหร่ก็จะเขียนเล่าไปเรื่อยเปื่อย แต่มิวายก็ต้องมายุ่งบ้างเพราะ CPU ชักจะเริ่มมีหลาย core

มีหลายกรณีนี่เลยที่ง่าย ๆ

1. เปิด app ขึ้นมาหลาย ๆ ตัวแล้วให้มันงานพร้อมกัน แต่เอาจริง ๆ อันนี้ 2 core ส่วนมากก็พอแล้ว
2. เขียนเว็บแบบธรรมดา ๆ นี่เองพอมีคนเข้ามาดูหลาย ๆ คนมันก็ใช้หลาย core เอง
3. เวลาเขียน script แบบที่ทำงานกับหลาย ๆ ไฟล์แยกกัน แต่ก่อนใช้ find | xargs ก็เปลี่ยนไปใช้ GNU Parallel แทน เช่น เวลาแปลงรูปด้วย ImageMagick แล้วสั่ง convert พร้อม ๆ กัน

เวลาทำแบบข้างบนได้ส่วนมากก็พึ่งพาความสามารถของ OS เช่น GNU/Linux หรือ Windows ที่มันทำได้หลาย ๆ งานพร้อมกันอยู่แล้ว รวมถึงกรณีของเว็บก็พึ่ง web server ด้วย บางทีก็พึ่ง Database ด้วย

จากตัวอย่างข้างบนเราก็เขียนโปรแกรมธรรมดา ๆ แบบเดิม ๆ มันก็ใช้หลาย core ได้ มากไปกว่านั้นดูเหมือนกว่างานของ programmer ส่วนมากก็จะเข้าข่ายกรณีนี้ด้วย คือไม่ต้องทำอะไรพิเศษ

พอมาดูเครื่องมือเรื่อง word embedding และ artificial neural network เช่นพวก PyTorch Tensorflow แค่บอกประมาณว่าเอา tensor มาทำอะไรกัน เดี๋ยว framework ก็จะไปจัดให้ใช้หลาย core ให้เอง หรือแม้แต่ใช้ GPU ก็ได้

แต่ก็มีบางทีมีบางทีที่โปรแกรมที่เขียนขึ้นมาเองมันช้าแล้วอยากจะใช้หลาย ๆ core บ้าง ที่แรกที่ผมนึกออกเลยก็คือใช้ pmap แทน map; map นี้ถ้าใครเขียนโปรแกรมแบบ functional programming อยู่แล้วก็คงใช้บ่อย หลาย ๆ กรณีก็เอามาใช้แทน for-loop พอเปลี่ยนจาก map เป็น pmap โปรแกรมมันใช้หลาย core เองเลยแก้แค่นี้เลย

อีกท่าคือใช้ thread pool ท่านี้ก็มักจะใช้ library หรือจะเขียนเองก็ตามแต่ มาสร้าง thread ไว้ก่อน ปกติแล้วก็เอาเท่าจำนวน core เลย หรือถ้าใช้ hyper thread ก็เท่าจำนวน thread ที่ cpu นั้นรับได้พร้อมกัน แล้วก็เอางานไปเข้า queue ไว้แล้ว thread pool มันจะดึงงานใน queue ไปแจกใส่ thread ที่ว่างงานอยู่

ส่วนมากข้อมูลระหว่าง thread ถ้าต้องส่งไปมาช่วงนี้ผมก็มักจะใช้ channel แบบที่ใครเขียน Go ก็คงได้ใช้กันบ่อย ๆ ผมได้ลองเล่นครั้งแรกก็ตอนเขียน Go ราว ๆ ปี 2013 หลายท่านบอกมาว่าจริง ๆ มีมาตั้งแต่ Limbo ตอนนี้ก็ใช้ได้ทั้งใน Rust และ Clojure ด้วย ภาษาอื่น ๆ ก็คงจะมีเหมือนกันแต่ผมไม่เคยเขียน

ไม่ใช่ข้อมูลทุกอย่างที่จะเหมาะกับการส่งไปใน channel บาง อีกท่าหนึ่งคือ shared memory มันควรจะเร็วกว่าส่งไปใน channel ปกติท่านี้มันก็ควรจะง่าย ๆ ถ้าอ่านข้อมูลอย่างเดียวไม่เขียน พอเขียนก็ชักเป็นเรื่อง ก็ต้องมีเรื่อง mutex lock หรืออื่น ๆ เข้ามา ใน Rust เห็นว่ามี atomic type ด้วย เข้าใจว่าเอามาจาก C++ อีกที
ผมมองว่าทั้งข้อดีและความวุ่นวายต่าง ๆ ของ Rust มันมาอยู่ที่ตอนเขียน parallel แบบ shared memory นี่เอง type system มัน check ได้เลยว่าต้อง lock ตัวแปรไหนบ้าง จริง ๆ พวก mutex lock นี้จะใช้ Go หรือ C เขียนเอาก็ได้ แต่ว่าจะ lock ตรงไหนก็ขึ้นกับ programmer ทาง compiler ไม่ค่อยได้ช่วยอะไรมาก แต่ประมาณว่าแค่เขียน linked list ให้แก้ link ได้ก็ปวดหัวได้

 

cbindgen #rustlang

ในโลกเรามีโปรแกรมที่เขียนด้วย C/C++ อยู่เยอะแยะทีนี้มี Rust ขึ้นมาหลายคนก็อยากจะเขียน Rust บ้าง แต่ก็ไม่จำเป็นต้องไปเขียนโปรแกรมเดิมด้วย Rust ใหม่ทั้งหมดก็ได้ อาจจะเขียนบาง module แล้วให้ C/C++ มาเรียก module ที่ว่านี้แทน ใช้ Rust ทำท่านี้ได้ง่ายไม่ต้องกังวลว่า garbage collector จะเริ่มทำงานแล้วหรือยังหรือไปตีกับตัวอื่นหรือเปล่าเพราะมันไม่ต้องใช้

แต่ปัญหาคือ Rust มันไม่มี C header ก็เลยมีคนเขียนโปรแกรมสร้าง c header พวก .h ทั้งหลายให้อัตโนมัติจาก source code ของ Rust ทีนี้ก็ต่อกันได้สบายขึ้น จากที่อ่านผ่าน ๆ ก็เป็นท่าที่ Firefox ใช้ด้วย

http://dreamingofbits.com/post/generating-c-bindings-for-rust-crates-with-cbindgen/

ชื่อไฟล์ที่ยาวที่สุด

ผมทดลองบน Xubuntu 16.04

ลองสั่ง touch

ใช้ EXT4

ชื่อไฟล์อักษรไทยที่ยาวที่สุดคือ:

๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔

ได้ความยาว 85 ตัวอักษร

พอลองอักษรโรมัน/ลาตินได้

012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234

ได้ 255 ตัวอีกษร
 
ที่นี้เลยลองบน NTFS บ้าง

อักษรไทยได้: ๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔๕๖๗๘๙๐๑๒๓๔

นับได้ 255 ตัวอักษร

ส่วนอักษรโรมัน/ลาตินได้

012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234

นับได้ 255 ตัวอักษรเท่ากัน

สรุปง่าย ๆ ว่าบน EXT4 ประหลาดคือเก็บชื่ออักษรไทยได้สั้นกว่าลาตินซะงั้น น่าจะเพราะว่าใช้ UTF-8 แล้วความยาวนับ byte เอา ลองเอาความยาวมาดู 85 คูณ 3 ได้ 255 พอดี ที่คูณ 3 เพราะอักษรไทย 1 ตัวใช้ 3 byte ใน UTF-8 ส่วนลาตินที่อยู่ใน ASCII ใช้ 1 byte ส่วน NTFS ลอยตัวเพราะใช้ UTF-16 ทั้งไทยและลาตินใช้ 2 byte เท่ากัน

ตีตัวออกห่าง node.js

2-3 ปีก่อนเคยคิดว่า ควรจะเขียน JavaScript เพราะว่าจะได้ย้าย code ไปมาระหว่าง บน web browser และ server ที่ส่วนมากใช้ node.js ได้เลย ซึ่งมันก็ทำได้จริง ๆ โดยไม่ต้อง compile ต่างหาก

 

แต่พอมาช่วงนี้ ES6 มาแล้วแต่ web browser ก็ใช้ได้บ้างไม่ได้บ้างก็ต้องเอา ES6 ไป compile ออกมาเป็นอย่างอื่นอยู่ดี ทำให้รู้สึกว่าแบบนี้ไม่ต้องเขียน JavaScript ก็ได้

 

พอมาดู Clojure/ClojureScript มันก็เขียนทีเดียวใช้ได้บน web browser และที่ server เลยเหมือนกัน ได้กระทั่งย้าย HTML Template ไปได้เลย ตอนนี้ดีไม่ดี Kotlin ก็อาจจะทำได้เหมือนกันแล้ว หรือถ้าใช้เฉพาะ web browser ใหม่ ๆ แม้แต่ Rust ก็ทำเป็น compile WebAssembly ได้เลย

 

เดี๋ยวนี้สำหรับผมก็เลยคิดว่าไม่จำเป็นต้องทำอะไรกับ node.js หรือแม้กระทั้งจริงจังกับ ES6 แบบมาก ๆ แล้ว

ใช้ eclipselink กับ tomee-embedded maven plugin ไม่รอด

ขนาดว่าใส่ eclipselink เข้าไปใน dependency แล้วก็ยังใช้ไม่ได้บอกว่าหา JMX Base อะไรสักอย่างไม่เจอทั้ง ๆ ที่มันก็อยู่ใน package นั้นล่ะ เดา ๆ ว่า jar ของ eclipselink ควรจะไปอยู่ใน lib ของ tomee-embedded เลย แต่ไม่ไหวล่ะ

จะเขียน web แบบใช้ WebAssembly ไปเลยได้ไหม ?

ผมว่ามันทำได้ crate นี้เขาเรียก alert ของ JS จาก Rust ได้เลย แล้ว target เป็น WebAssembly ด้วย มี demo ให้ดูด้วย เรียก alert ได้เรียกอย่างอื่นก็น่าจะได้

อีกโครงการหนึ่ง stdweb เขาจัดการเรื่อง interop ให้ Rust ไปเรียก function ของ JavaScript ได้ เช่น สั่ง:


document().query_selector(...)


ใน Rust ได้เลย แต่ดูเหมือน target ยังเป็น asm.js อยู่ แต่ต่อไปจะทำเป็น WebAssembly แทนก็คงจะได้

ถ้าสมมุติว่าเขียน web แล้วต้องมา align protein sequence บน web browser กันเลย หรือคำนวณอะไรอย่างอื่นหนัก ๆ compiler มาเป็น WebAssembly มันก็คงเร็วขึ้น แต่ถ้าแค่เอามา regular expression มา check ว่าเบอร์โทรศัพท์ที่กรอกในฟอร์มถูกหรือเปล่า ใช้ WebAssembly ไปว่าก็ไม่น่าจะมีประโยชน์ ดีไม่ดีจะช้าลงด้วยหรือเปล่าก็ไม่ทราบ