Tech Talks @NSU: Теоретические основы программирования: проекции Футамуры-Турчина и частичные вычисления. Можно ли написать компилятор для интерпретируемого языка.

  • Published on
    19-Jan-2017

  • View
    57

  • Download
    1

Embed Size (px)

Transcript

  • - .

  • ( , ) S S S

    MS

  • Palindrom { s.1 e.2 s.1 = ; s.1 = True ; = True; e.1 = False ; }

  • Lisp (defun palindrome( L ) (cond ((null L) T ) ((equal (car L) (car (last L))) (palindrome (cdr (reverse (cdr L))))))) (palindrome '(bob))

  • , .

    :

  • f x 1 = x f x 0 = 1 f x n = x * f x (n-1) s x = f x 2 ----- s x = x * x

    funcwon f(x, n) { if (n===0) return 1; if (n===1) return x; return x * f(x, n-1);

    } funcwon s(x) {

    return f(x, 2); } funcwon s(x) {

    return x*x; }

  • (s (p, x)) (y) = p (x, y) pL(d) = r intLR (p, d) = r s (intLR ,p) (d) = r 1- s (s, intLR) (p) (d) = r 2- s (s, s) (intLR) (p) (d) = r

  • :

    : :

  • hp://blog.sigfpe.com/2009/05/three-projecwons-of-doctor-futamura.html

  • ?

    1977

    Datalogisk Inswtut p Kbenhavns Universitet () Lisp 15

  • ?

    , , (. supervising compiler)

  • data N = Z | S N 0 Z, 1 S Z, 2 S (S Z), 3 S (S (S Z)) . . ( .. )

  • (driving) : data N = Z | S N add x Z = x add x (S y) = S (add x y) add2 x = add x (S (S Z)) : data N = Z | S N add2 x1 = S (S x1)

    : add2 x1 add x1 (S (S Z)) S (add x1 (S Z)) S (S (add x1 Z) S (S x1)

  • : f(x,y) fA(y) = f(A, y).

    : f(x), g(x) fg(x) = f(g(x)).

    : f(x) f-1(y) = x, y = f(x).

  • Self-hoswng

    Ada, BASIC, C, CoffeeScript, F#, FASM, Forth, Haskell, Java, Lisp, Modula-2, OCaml, Oberon, Pascal, Python, Scala, Smalltalk, and Vala

    -

  • 1990

  • 1 +!+[] 18 + 78 +(+!+[]+[!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+!+[]])+(+(!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+[!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+!+[]+!+[]]))

    hp://discogscounter.gereehoswng.co.uk/js-noalnum_com.php

  • . . CILPE: -

    .. ..

    Three Futamura Projecwons (hp://habrahabr.ru/post/47418/)

    The Three Projecwons of Doctor Futamura (hp://blog.sigfpe.com/2009/05/three-projecwons-of-doctor-futamura.html)

    JavaScript (hp://habrahabr.ru/post/112530/)

Recommended

View more >