Advanced Web Development and Formal Languages Overview

UFCFR5-15-3 Advanced Topics in Web Development II 2021/22 F# part 1 functional programming & code examples 1

Formal languages (syntax and grammar): In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consist of symbols, letters, or tokens that concatenate into strings of the language.Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called well-formed words or well- formed formulas. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. Wikipedia. Lecture 3

Formal languages, Turing completeness & programming languages Modern programming languages are Turing complete because they each implement all the features required to run programs like addition, multiplication, if-else condition, return statements, ways to store/retrieve/erase data and so on. Lecture 3

Models of Computing Church Turing thesis shows models are equivalent (in 1927) Alonzo Church (1903 1995) Alonzo Church (1903 1995) Alan Turing (1912 1954) computer scientist, mathematician, logician, cryptanalyst and theoretical biologist, marathon runner American mathematician and logician Lambda calculus Computing modelled as relationships between mathematical functions. Turing Machine Computing modelled as an abstract state machine.

Von Neumann Architecture (1) The von Neumann architecture, which is also known as the von Neumann model and Princeton architecture, is a computer architecture based on that described in 1945 by the mathematician and physicist John von Neumann and others in the First Draft of a Report on the EDVAC.[1]This describes a design architecture for an electronic digital computer with parts consisting of a processing unit containing an arithmetic logic unit and processor registers; a control unit containing an instruction register and program counter; a memory to store both data and instructions; external mass storage; and input and output mechanisms. John von Neumann (1903-1957) mathematician, physicist, inventor, computer scientist, set theorist, polymath Von Neumann Architecture

Von Neumann Architecture (2)

Von Neumann Architecture (3) A program is just data: Stored Program concept. A program is a series of steps. Steps execute in linear sequence. Steps alter memory registers. Steps can alter the next step.

Imperative Programming Imperative mood Series of precise commands State: values that get changed over time by commands The purpose of commands is to alter state This is all modern hardware does

Procedural Programming Imperative Programming Evolved Procedure = subroutine = reusable chunks of code Structured Programming: higher level of abstraction if-then while for

Procedural Program Var MyList [3, 7, 2, 5, 9, 4] Var Biggest Define and set variables a list and a string Define Procedure Procedure FindBiggest For MyList As Item If Item > Biggest Then Biggest = Item End If End For End Procedure Set Biggest to Item if Item > Biggest End Procedure Definition Call Procedure Call FindBiggest Print Biggest Print value in variable

Imperative program example: XML processing using PHP

An imperative loop for Beer Drinking (we ll come back to this one later ) Choose beer from menu Order a beer Start Drink the beer The beer arrives

Functional (declarative) Programming

Functional Programming Languages: a little history LISP developed in the early 1950 s at MIT for the IBM 700/7000 series of scientific computers by John McCarthy. Lisp introduced many key features now found in functional languages. Scheme(1970 s MIT) and Dylan(1990 s Apple) were later attempts to simplify and improve Lisp. IPL - Information Processing Language developed at Rand Corporation around 1956 - supporting lists, dynamic memory allocation, data types, recursion & functions as arguments. John McCarthy (1927-2011) APL developed in the early 1960s by Kenneth E. Iverson, described in his 1962 book A Programming Language (ISBN 9780471430148). APL was the primary influence on John Backus's FP ideas (see next slide). ML(Meta Language) was created (1970 s) by Robin Milner and David Turner. Turner went onto develop the language SASL (St Andrews Static Language) and later the language Miranda (1985). ML eventually developed into several dialects, the most common of which are now Objective Caml and Standard ML. Kenneth Eugene Iverson (1920-2004) https://images-na.ssl-images-amazon.com/images/I/51oQRrIRT6L._SX328_BO1,204,203,200_.jpg Haskell - language began with a consensus in 1987 to form an open standard for functional programming research; implementation releases have been ongoing since 1990. SCHEME CLOJURE

John Backus, Turing Award Lecture, 1977 MILESTONE Inventor of the FORTRAN programming language so he knew all about imperative programming!

From the Backus paper (1977) An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often non- repetitive and non-recursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining formscan use high level programs to build still higher level ones in a style not possible in conventional languages.

Combining forms canuse high level programs to build still higher level ones OO pattern/principle o Single Responsibility Principle o Open/Closed principle o Dependency Inversion Principle o Interface Segregation Principle o Factory pattern o Strategy pattern o Decorator pattern o Visitor pattern FP equivalent o Functions o Functions o Functions o Functions o You will be assimilated! o Functions again o Functions o Resistance is futile! pure functional programs are fractal in structure I d rather write programs that write programs than write programs

Functional Programming: a working definition Functional programming (often abbreviated FP) is the process of building software by composing pure functions, avoiding shared state, mutable data, and side-effects. Functional programming is declarative rather than imperative, and application state flows through pure functions. Contrast with object oriented programming, where application state is usually shared and co-located with methods in objects.

Functional Programming helps us write code that is: o Easier to understand and debug; o Cheaper and easier to maintain; o More legible; o More reusable; o More testable; o Less error prone.

To accomplish this, we follow a few general rules: 1. Use functions over loops wherever possible; 2. Always return the same result given the same arguments; 3. Write functions that do one thing.

Code Examples

Using a foreach() loop to double numbers in an array: imperative code example 1

Using a for() loop to double numbers in an array: imperative code example 2

Lambda ( ) functions: A lambda is an anonymous function, a function defined with no name that can be stored in a variable and that can be passed as an argument to other functions or methods. In other words, lambda functions are simply throwaway functions that can be defined at any time and are normally attached to a variable. The lambda functions only exist as long as the variables of which they are defined exist, so when that variable goes out of scope, so does the function. Lambda functions are useful for a number of instances, most notably for many PHP functions that accept a callback function. One such function is array_map(), which allows us to walk through an array and apply a callback function to each element of the array.

Map with Lambda ( ) function (PHP): test: output:

Map with Lambda ( ) function (JavaScript): test: output:

Lambda ( ) function assigned to variables(PHP): simple bit checking test: output:

Lambda ( ) functions used in-place with array_filter(): test: output:

Lambda ( ) functions in JQuery:

Pure functions: o No side-effects (including I/O) o Explicit function input/output o Stateless o Takes clear input, gives clear output - referential transparency All mathematical functions are pure functions, whereas date(), time(), rand(), etc. are impure.

A pure & useful function (PHP) test1: test2:

Immediate benefits of using pure function: oEasy Testability supports Test Driven Development (TDD) oNot SAD (Spooky Action at a Distance) oSelf-contained oNo I/O oIdempotent

next lecture: composability higher-order functions recursion immutability lists currying referential transparency closures