Understanding FIZ: A Simple Functional Programming Language
FIZ is a functional programming language that uses only integers and supports basic features like incrementing, decrementing, and conditional expressions. Functions are defined in a simple manner, and errors can be handled using the "halt" command. The language emphasizes recursion over loops and features lazy evaluation to optimize performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS252: Systems Programming Ninghui Li Topic 3: Programming in a FIZ: Simple Functional Programming Language
What is FIZ FIZ F is for functional programming I is for integer Z is for zero, denoting the simplicity of the language In Functional Programming, one defines functions writes expressions Syntax: instead of writing f(a, b, c); we write (f a b c) (we only use integer data type) slide 2
Basic Features of FIZ non-negative integer evaluates to its value (inc exp) evaluates to value of exp + 1 (dec exp) evaluates to halt if value of exp is 0 otherwise evaluates to value of exp - 0 (ifz cexp texp fexp) evaluates to value of texp when cexp evaluates to 0 and to value of fexp when cexp evaluates to none 0 slide 3
Examples (inc 3) (inc (dec (inc 1))) (ifz (dec 1) 2 3) 4 2 2 slide 4
Defining New Functions (define (name arguments) function-body ) Examples: (define (add x y) (ifz y x (add (inc x) (dec y)))) (define (sub x y) (ifz y x (ifz x halt (sub (dec x) (dec y))))) (name arguments) E.g., (add 2 3); (add (inc 2) (dec 3)) slide 5
Dealing with Errors (halt) stops the program Whenever the evaluation could lead to non- integer or negative number, call (halt) Note: FIZ has no assignment, except in function invocation. FIZ has no loop, except in recursion slide 6
More Examples: Add (define (add x y) (ifz y x (add (inc x) (dec y)))) ; if y==0, x+y=x ; otherwise x+y = (x+1) + (y-1) We assume lazy evaluation, i.e., in (ifz cond t_exp e_exp) We evaluate t_exp only when cond is 0, and evaluate e_exp only when cond is not 0
Lazy versus Eager Evaluation In Lazy evaluation In Eager evaluation (add 3 0) (add 3 0) becomes becomes (ifz 0 3 (add (inc 3) (dec 0))) (ifz 0 3 (add (inc 3) (dec 0))) We do not evaluate the last We need to evaluate the last argument in the above function call, i.e., argument yet, and figures out that we do not need it (add (inc 3) (dec 0)), Which becomes (add 4 -1) This then becomes infinite loop A similar issue in C: In If (cond_1 && func(a,b)) , if cond_1 is false, would func(a,b) be called?
More Examples (define (mul x y) (ifz y 0 (add x (mul x (dec y)))) (define (div x y) (ifz y (halt) (ifz (lt x y) 0 (inc (div (sub x y) y)))))
Concept of Public Key Encryption In Traditional Cryptography, encryption key = decryption key, and must be kept secret, and key distribution/agreement is a difficult problem to solve In public key encryption, each party has a pair (K, K-1) of keys: K is the public key, and used for encryption K-1 is the private key, and used for decryption Satisfies DK-1[EK[M]] = M Knowing K, it is computationally expensive to find K-1 The public key K may be made publicly available, e.g., in a publicly available directory Many can encrypt, only one can decrypt Public-key systems aka asymmetric crypto systems
RSA Algorithm Invented in 1978 by Ron Rivest, Adi Shamir and Leonard Adleman Published as R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp120- 126, Feb 1978 Security relies on the difficulty of factoring large composite numbers Essentially the same algorithm was discovered in 1973 by Clifford Cocks, who works for the British intelligence
RSA Public Key Crypto System Key generation: 1. Select 2 large prime numbers of about the same size, p and q Typically each p, q has between 512 and 2048 bits 2. Compute n = pq, and (n) = (q-1)(p-1) 3. Select e, 1<e< (n), s.t. gcd(e, (n)) = 1 Typically e=3 or e=65537 4. Compute d, 1< d< (n) s.t. ed 1 mod (n) Knowing (n), d easy to compute. Public key: (e, n) Private key: d
RSA Description (cont.) Encryption Given a message M, 0 < M < n M Zn {0} use public key (e, n) compute C = Me mod n C Zn {0} Decryption Given a ciphertext C, use private key (d) Compute Cd mod n = (Me mod n)d mod n = Med mod n = M
RSA Example p = 11, q = 7, n = 77, (n) = 60 d = 13, e = 37 (ed = 481; ed mod 60 = 1) Let M = 15. Then C Me mod n C 1537 (mod 77) = 71 M Cd mod n M 7113 (mod 77) = 15 Topic 6: Public Key Encrypption and Digital Signatures 14
We show how to do modular exponentiation in FIZ. (define (mexp x e y) (ifz e 1 (ifz (rem e 2) (rem (square (mexp x (div e 2) y)) y) (rem (mul x (mexp x (dec e) y)) y)))) If e==0, then result is 1 Else if e%2=0, result is (x^(e/2) mod y) ^ 2 mod y Else result is (x * (x^(e-1) mod y)) mod y Topic 6: Public Key Encrypption and Digital Signatures 15
FIZ is based on Scheme Scheme is a functional programming language Uses the list data structure extensively Program/Data equivalence Heavy use of recursion Garbage-collected, heap-allocated Usually interpreted, but good compilers exist 16
History of Function Programming Lisp was created in 1958 by John McCarthy at MIT Stands for LISt Processing Scheme developed in 1975 A dialect of Lisp Racket ML OCaml Haskell 17
Application Areas Artificial Intelligence expert systems planning Simulation, modeling Rapid prototyping 18
Functional Languages Imperative Languages Ex. Fortran, Algol, Pascal, Ada based on von Neumann computer model Functional Languages Ex. Scheme, Lisp, ML, Haskell Based on mathematical model of computation and lambda calculus 19
Review Be able to write simple programs in FIZ. Know the concept of lazy evaluation versus eager evaluation. How RSA work is not required. 20
Upcoming Attraction How to write an interpreter/compiler frontend? Topic 4: Regular expressions & Lexical Analyzer Topic 5: Context-free grammar & Parser 21
