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

• View
57

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)

• : 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/)