Upgrade to Pro — share decks privately, control downloads, hide ads and more …

tacit programming : Point-free, Concatenatives & J

tacit programming : Point-free, Concatenatives & J

tacit programming : Point-free, Concatenatives & J

さっちゃん

December 26, 2019
Tweet

More Decks by さっちゃん

Other Decks in Programming

Transcript

  1. Example 1 : factorial Non-point-free factorial n = n *

    factorial (n - 1) factorial 0 = 1 factorial 9
  2. Example 2 : average Non-point-free average xs = foldr (+)

    0 xs / (fromIntegral . length $ xs) average [2, 3]
  3. Example 2 : average point-free average = ((/) . foldr

    (+) 0) <*> (fromIntegral . length) average [2, 3]
  4. combinatory logic An raugh image of combinators is, that λx.1+x

    becomes + 1 x . + 1 the part of it makes sence. 1 x also makes sence.
  5. One of a form of combinatory logic is SKI combinator

    calculus Sxyz=xz(yz) S copies z. Kxy=x K discards y. Ix=x I is identity. SKI is Turing complete.
  6. concatenative programming language Add in Forth. 2 3 + 1.

    Put 2 on the stack. 2. Put 3 on the stack. 3. Pop 3 & 2 from the stack, then plus them, put the result 5 on the stack.
  7. concatenative programming language If 3 + evaluated lazily it makes

    sence. 1. Put 3 on the stack. 2. Pop 3 & another value from the stack, then plus them, put the result ont the stack. concatenative programming language like Factor & Popr do this.
  8. Example 1 : average in Popr. average: dup sum swap

    length /f [2 3] averge concatenatives are always tacit.
  9. Example 2 : factorial in Factor. : factorial_rec ( n

    n -- n ) dup 0 = [ drop ] [ [| n m | n m * m 1 - factorial_rec ] call ] if ; : factorial ( n -- n ) dup 0 < [ drop 0 ] [ 1 swap factorial_rec ] if ; 9 factorial [ ] is quotatin. It's evaluated in lazy.
  10. Example 2 : factorial another one in Factor. MEMO: factorial

    ( n -- n! ) dup 1 > [ [1,b] product ] [ drop 1 ] if ; 9 factorial
  11. Example 2 : factorial in Popr factorial: [1 == 1

    swap !] [dup dup 1 - factorial * swap 1 > !] | pushl head 9 factorial 1 == 1 swap ! fails when the value is greater than 1. dup dup 1 - factorial * swap 1 > ! fails when the value is 1.
  12. concatenative programming language is a only way to extends conbinatory

    logic? is a only way to extends pipe & filter?
  13. J

  14. Example 1 : add +/2 3 5 2 3 is

    a vector. / is fold. So +/ sums the vector.
  15. Example 2 : average Evaluation flow. (+/ % #) 2

    3 (+/ 2 3) % (# 2 3) NB. monadic fork monadic fork : (fgh)x=(fx)g(hx)
  16. Example 3 : factorial Evaluation flow. J evaluates a program

    from right. */ 1 + i. 9 */ 1 + 0 1 2 3 4 5 6 7 8 NB. `i.` creates a vector */ 1 2 3 4 5 6 7 8 9 NB. vector operation 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 NB. fold `*` 362880
  17. Example 3 : factorial another tacit one. factorial =: 1:

    ` (* factorial@<:) @. * factorial 9 362880
  18. Example 3 : factorial Evaluation flow. factorial 2 1: `

    (* factorial@<:) @. * 2 (* factorial@<:) 2 NB. `@.` selects the second 2 * (factorial@<: 2) NB. monadic hook monadic hook : (fg)x=xf(gx)
  19. Example 3 : factorial Evaluation flow. 2 * (factorial@<: 2)

    2 * (factorial 1) 2 * (1 * (factorial 0)) NB. same as `factorial 2` 2 * (1 * (1: ` (* factorial@<:) @. * 0)) 2 * (1 * (1: 0)) NB. `@.` selects the first 2 * (1 * 1) 2 * 1 2