Advanced Functional And Logic Programming
Advanced Functional and Logic ProgrammingLecture 5: Introduction to Functional Programming.The Racket languageMircea Marinmircea.marin@e-uvt.roOctober 25, 2018M. MarinALFP
Introduction to FPCharacteristic featuresDescribe every computation as a request to evaluate anexpression, and use the resulting value for something.Main notions: function, value, expression.program: collection of function definitions in themathematical senseThe value of a function call depends only on the values of thefunction arguments.expression (typically) a combination of nested function calls.computation evaluation of an expression a value.value element of a datatype (string, integer, list, etc.) thatcan benamedstored in a composite data (e.g., element of a list or vector)passed as argument to a function callreturned as result of a function callM. MarinALFP
Characteristic features of FPVariables are just names given to valuesThere is no assignment we can not change the value of avariable we can not define repetitive computations by iteration. we define repetitive computations by recursionFunctions are values we can havefunctions that take function argumentsfunctions that return functions as resultslists of functions, etc.M. MarinALFP
Example 1: Computation of n! by recursionWe can not define fact by iterationfact(int n)i 1; fact: 1;if(i n)i: i 1;fact: fact*i;endifreturn factbecause there is no assignment in functional programming.But we can define fact by recursion (pseudocode)fact(int n)if (n 1)1elsen*fact(n-1)M. MarinALFP
Example 2: A function with a function argumentmap(f , L) takes as inputs a function f : A B and a listL (a1 , a2 , . . . , an )of elements from Aand returns the list(f (a1 ), f (a2 ), . . . , f (an ))of elements from BAssume thatempty(L) recognises if L is empty listfirst(L) returns the first element of a listrest(L) returns the list produced by removing the first element of Lprepend(e,L) adds element e in front of list Lmap(f,L)if (empty(L)) Lelse prepend(f(first(L)),map(f,rest(L)))M. MarinALFP
Why learn functional programming?It has a very simple model of computation:Programs consist (mainly) of function definitionsComputation evaluation of (nested) function callsWe can define higher-order functions (functions that takefunctions as arguments and/or return functions as results) we can write highly modular and reusable code[Hughes:1989]According to [Thompson:1999]:“Functional languages provide a framework in which thecrucial ideas of modern programming are presented in theclearest possible way. This accounts for their widespread use inteaching computing science and also for their influence on thedesign of other languages.”M. MarinALFP
Functional programmingWhat will we learn?How to use DrRacket to write and run functional programsI DrRacket is an integrated development environment (IDE) forRacket, the current dialect of SchemeI DrRacket is freely available to be installed on Windows, Linux,MacOS, etc.https://racket-lang.orgWhen started, DrRacket shows a window with two panels:1the definitions area, where you can start typing your ownprograms, save them for later use and run them.2the interactions area, where you can interact directly with theinterpreter of Racket.M. MarinALFP
Functional programming languagesEarly historyThe first high-level programming language was Fortran(1957). Fortran is an imperative programming language.The second high-level programming language was Lisp (1958).Designed by people interested in AI (”the science andengineering of making intelligent machines”);Lisp became the favoured language for AI researchLisp is acronym for ”List Processing”: Lists are used torepresent both source code and composite data.Initial Lisp had no standard specification many dialects ofLisp appeared people were confused, and wanted astandardised and reliable version of Lisp Common Lisp (ANSI 1994 standard): extensive libraries, idealfor writing commercial software Scheme (IEEE 1990 standard): wonderful for educationalpurposes.The most recent dialect of Scheme is Racket.M. MarinALFP
Lisp and its dialectsCharacteristic featuresThey are strict programming languagesI A language is strict if the evaluation of function calls proceedsas follows: First, we compute the values of the arguments, andnext we call the function with the computed values.Example4 ((2 2) (4 3)) is the infix notation for the nested functioncall (4, (0, (4, 3))). The strict evaluation of this expression is: (4, ( (2, 2), (4, 3))) (4, (0, (4, 3))) (4, (0, 1)) (4, 0) 4All expressions are written in a peculiar syntax, called theparenthesised prefix notation (see next slide)M. MarinALFP
The parenthesised prefix notationEvery function call f (e1 , e2 , . . . , en ) is written as(f pe1 pe2 . . . pen )where pe1 , pe2 , . . . , pen are the parenthesised prefix notationsof e1 , e2 , . . . , enEvery other composite programming construct is of the form(form-id .)where form-id is the identifier of the programming construct.Characteristics of the parenthesised prefix notationEvery open parenthesis has a corresponding close perenthesisInstead of comma, we type whitespace (one or more blanks,newlines, tabs, etc.)M. MarinALFP
The parenthesised prefix notationExamples((2 7)/3-1)*(7-4) is written as(* (- (/ ( 2 7) 3) 1) (- 7 4))The parenthesised prefix notation ofif (n 1) 1 else n*fact(n-1)is(if ( n 1) 1 (* n (fact (- n 1))))RemarkThe parenthesised prefix notation ofif cond expr1 else expr2is (if cond-pe expr1 -pe expr2 -pe)where cond-pe, expr1 -pe, expr2 -pe are the parenthesised prefixnotations of cond, expr1 , expr2 .M. MarinALFP
RacketValues and built-in datatypesValues are the simplest expressions: they evaluate to themselfA value is either atomic or composite.Every value belongs to a datatype.Datatypes with atomic values:integer: 1 -703 12345678999999floating-point: 1.23 3.14e 87string: "abc"symbol: ’abc(symbol values are preceded by the quote character’)boolean: #t (for truth) #f (for falsehood).Some datatypes have composite values: pairs, lists, vectors,hash tables, etc.A composite value is a collection of other values.Composite values and datatypes will be described in Lecture 2.M. MarinALFP
Interacting with DrRacketThe Read-Eval-Print loop (REPL)In the interactions area, at the input prompt Type in an expression e in parenthesised prefix notation, andpress Entere will be read, evaluated, and the resulted value will beprinted on the next line in the interactions area.M. MarinALFP
Interacting with DrRacketThe Read-Eval-Print loop (REPL): ExampleExamplethe nesting of parentheses clarifies the order in which thefunction applications should be performedthe semicolon ; starts a comment (highlighted with brown)that extends to the end of the linecomments are ignored by the interpreterM. MarinALFP
Expressions and definitionsThe interpreter of Racket recognises two kinds of input forms:Expressions: An expression expr is read, evaluated, and its value isprinted in the interactions area.Definitions: A definition is of the form(define var expr )Definitions are interpreted as follows:expr is evaluated, and its value is assigned tovariable var .Afterwards, var can be used to refer to the valueof expr .pExample (Compute x 2 y 2 for x 2 and y 3) (define x 2) (define y 3) (sqrt ( (* x x) (* y y)))3.605551275463989M. MarinALFP
Function definitionsThe meaning of an expression(lambda (x1 . . . xn ) body )is “the function which, for the values of arguments x1 , . . . , xn ,computes the value of body .”The evaluation of this expression creates a function, which isa value that can be assigned to a variable.Example (the factorial function) (define fact(lambda (n)(if (or ( n 0) ( n 1))1(* n (fact (- n 1)))))) (fact 5) ; compute 5!120M. MarinALFP
Composite datatypesEvery composite datatype has:recognizers boolean functions that recognize values of thattype.constructors functions that build a composite value fromcomponent valuesselectors functions that extract component values from acomposite vulueutility functions useful functions that operate on//withcomposite valuesA specific internal representation that affects the efficiency ofthe operations on themM. MarinALFP
PairsThe simplest container of two valuesconstructor: (cons v1 v2 )internal representation: a cons-cell that stores pointers to theinternal representations of v1 and v2v1v2(cons? p): returns #t if the value of p is a pair, and #fotherwise.selectors(car p): returns the first component of pair p(cdr p): returns the second component of pair pDiagrammatically, these operations behave as follows:v1v2conscar(cons v1 v2 )pair?#tM. MarinALFPcdrv1v2
Operations on pairsExamples (define p (cons 1 "a")) p’(1 . "a") (pair? p)#t (car p)1 (cdr p)"a" (define q (cons ’a ’b)) q’(a . b) (car q)’aRemarkWe can nest pairs to any depth to store many values in a singlestructure: (cons (cons (1 ’a) "abc"))’((1 . a) . "abc") (cons (cons ’a 1) (cons ’b (cons #t "c")))’((a . 1) b #t . "c")M. MarinALFP
The printed form of pairsRacket applies repeatedly two rules to reduce the number ofquote characters(’) and parentheses in the printed forms:rule 1: (cons v1 v2 ) is replaced by’(w1 . w2 )where w1 , w2 are the printed forms of v1 , v2 fromwhich we remove the preceding quote, if any.There is space before and after the dotcharacter in the printed form.rule 2: Whenever there is a dot character before aparenthesised expression, remove the dot characterand the open/close parentheses.M. MarinALFP
Printed form of pairsExample (cons (cons ’a 1) (cons ’b (cons #t (cons "c" ’d))))’((a . 1) b #t "c" . d)The printed form is obtained as follows:Apply rule 1 ro reduce the number of quote characters theform ’((a . 1) . (b . (#t . ("c" . d))))Apply repeatedly rule 2 to eliminate dots and open/closeparentheses:’((a . 1) . (b . (#t . ("c" . d)))) ’((a . 1) b . (#t . ("c" . d)))’((a . 1) b . (#t . ("c" . d))) ’((a . 1) . (#t "c" . d))’((a . 1) . (#t "c" . d)) ’((a . 1) b #t "c" . d)The final form is the printed form:’((a . 1) b #t "c" . d)M. MarinALFP
PairsPrinted formsWe can input directly the printed forms, which are usually muchshorter to write than combinations of nested cons-es:ExampleInstead of (cons (cons ’v11 ’v12) (cons ’v21 ’v22)) we cantype ’((v11 . v12) v21 . v22): (define p ’((v11 . v12) v21 . v22)) p’((v11 . v12) v21 . v22)) (car p) (cdr p)’(v11 . v12)’(v21 . v22) (car (car p)) (cdr (car p))’v11’v12 (car (cdr p)) (cdr (cdr p))’v21’v22M. MarinALFP
Selectors for nested pairsThe selection of an element deep in a nested pair is cumbersome: (define p ’(a ((x . y) . c) d))To select the second of the first of the first of the secondcomponent of p, we must type (cdr (car (car (cdr p))))’yWe can use the shorthand selector cdaadr: (cdaadr p)’yOther shorthand selectors: cx1 . . . xp r where x1 , . . . , xp {a, d}and 1 p 4 (max. 4 nestings)M. MarinALFP
ListsConstructors and internal representationA recursive datatype with two constructors:null: the empty list(cons v l): the list produced by placing the value v in frontof list l.If n 1, the list of values v1 , v2 , . . . , vn is(cons v1 (cons v2 . (cons vn null).))with the internal representation.v1v2vnRemark: The internal representation of a list with n valuesv1 , . . . , vn consists of n cons-cells linked by pointers.M. MarinALFP
Printed form of lists null’(); the printed form of the empty listAll non-empty lists are pairs, and their printed form is computedlike for pairs.Example (cons ’a(cons ’b(cons ’c (cons (cons ’d null)null))))’(a b c (d))This printed form is obtained by applying repeatedly rule 2 to theform ’( a. (b . (c . ((d . ()) . ()))))M. MarinALFP
ListsOther constructors and selectorsA simpler constructor for the list of values v1 , v2 , . . . , vn : (list v1 v2 . . . vn )Selectors:(car lst) selects the first element of the non-empty list lst(cdr lst) selects the tail of the non-empty list lst(list-ref lst k) selects the element at position k of lstNote: The elements are indexed starting from position 0.Example (list ’a #t "bc" ’d)’(a #t "bc" ’d) (list ’() ’a ’(b c))’(() a (b c)) (list-ref ’(1 (2) 3) 1)’(2) null’() (list-ref ’(1 2 3) 0)1M. MarinALFP
List recognizers(list? lst) recognizes if lst is a list.(null? lst) recognizes if lst is the empty list.Example (define lst ’(a b c d)) (list? lst)#t (car lst)’a (cdr lst)’(b c d) (list-ref lst 0)’a (list-ref lst 1)’bM. MarinALFP
List operationsDiagrammatic representation of their (list v0 . vn )null?list?#f#tM. MarinALFPi)vi
Utility functions on lists(length lst) returns the length ( number of elements) of lst (length ’(1 2 (3 4)))3 (length ’())0(append lst1 . . . lstn ) returns the list produced by joining listslst1 , . . . , lstn , one after another. (append ’(1 2 3) ’(a b c))’(1 2 3 a b c)(reverse lst) returns the list lst with the elements in reverseorder: (reverse ’(1 2 3))’(3 2 1)M. MarinALFP
Operations on lists (1)apply and filterIf f is a function and lst is a list with component valuesv1 , . . . , vn in this order, then(apply f lst)returns the value of the function call (f v1 . . . vn ).If p is a boolean function and lst is a list, then(filter p lst)returns the sublist of lst with elements v for which (p v) istrue.Examples (apply ’(4 5 6)); compute 4 5 615 (filter symbol? ’(1 2 a #t "abc" (3 4) b))’(a b) (filter number? ’(1 2 a #t "abc" (3 4) b))’(1 2)M. MarinALFP
Operations on lists (2)mapIf f is a function and lst is a list with component valuesv1 , . . . , vn in this order, then(apply f lst)returns the list of values w1 , . . . , wn where every wi is the value of(f vi )Example (map (lambda (x) ( x 1)) ’(1 2 3 4))’(2 3 4 5) (map list? ’(1 2 () (3 4) (a . b)))’(#f #f #t #t #f)M. MarinALFP
VectorsA composite datatype of a fixed number of values.Constructors:(vector v0 v1 . . . vn 1 )constructs a vector with n component values, indexed from 0to n 1, and internal representation0n 11.v1 v2vn(make-vector n v )returns a new vector with n elements, all equal to v .Recognizer: vector?Selectors: (vector-ref vec i)returns the component value with index i of the vector vec.M. MarinALFP
Operations on vectorsExample (define vec (vector "a" ’(1 . 2) ’(a b))) (vector? vec)#t (vector-ref vec 1)’(1 . 2) (vector-ref vec 2)’(a b) (vector-length vec) ; compute the length of vec3M. MarinALFP
Printed form of vectorsThe printed form of a vector with component values v0 , v1 , . . . , vnis’#(w0 w1 . . . wn )where wi is the printed form of vi from which we remove thepreceding quote character, if any.Examples (vector ’a #t ’(a . b) ’(1 2 3))’#(a #t (a . b) (1 2 3)) (vector ’a (vector 1 2) (vector) "abc")’#(a #(1 2) #() "abc") (make-vector 3 ’(1 2))’#((1 2) (1 2) (1 2))The printed forms of vectors are also valid input forms: ’#(1 2 3)’#(1 2 3) (vector? ’#(1 2 3))#tM. MarinALFP
The void datatypeConsists of only one value, ’# void :The recognizer is void?Attempts to input ’# void directly will raise a syntax error: ’# void read: bad syntax ‘# ’We can obtain ’# void indirectly, as the value of thefunction call (void): (list 1 (void) ’a)’(1 # void a) (void? (void))#tUsually, ’#void is not printed (void) ; nothing is printedM. MarinALFP
Block-structured programmingWhat is this?Block: sequence of definitions, expressions and otherblocks that ends with an expression.comp1.compnexprRepresentation:where the block components comp1 , . . . , compn are definitions,expressions, or blocks.Note: blocks can be nested.A block-structured language interprets a block as a singleexpression:Every variable declaration has a lexical scope: the textualportion of code where the name refers to that declaration.The scope of a variable declaration is the block where thevariable is declared. We also say that the variable is local tothat block.Block variables are visible only in the block where they aredefined.Nested block may shadow each other’s declarations.M. MarinALFP
Block-structured programming with RacketRacket is block-structured: We can evaluate the standaloneblockcomp1.compnexprwith the special form(local [ ] comp1 . compn expr )Remark(println expr )prints the value of expr on a new line, and returns the value # void .We will use println to illustrate how block-structured evaluationworks(see next slide )M. MarinALFP
Block-structured programmingIllustrated example (local [ ](define x 1)(local [ ](define x 2)(define y 3)(println ( x y)))(local [ ](define y 4)(define z 5)(println ( x y z)))( x 2))5103; x 2 shadows x 1; print the value of x y for x 2,y 3; print the value of x y z for x 1,y 4,z 5; return the value of x 2 for x 1Remark: This is a block with two sub-blocksM. MarinALFP
Special forms with blocksThe lambda-form for function definitions:(lambda (x1 . . . xn ) block)The cond-form(cond [test1 block1 ].[testn blockn ])evaluates test1 , test2 , . . . in this order until it finds the firsttesti whose value is true, and returns the value of blocki .If all expressions testi evaluate to #f, the value of thecond-form is # void RemarksIn Racket, any value different from #f acts as true. E.g.:I "abc", ’abc, null, 0, ’(1 2), #t are true values.I #f is the only value which is not true.M. MarinALFP
Special forms with blocksExample: the cond-formLet’s define the numeric function f : R R R( (y x 2 ) if x 2 y ,21 f (x, y ) p y xp( x y ) ( x y )2 if x 2 y .(define (f x y)(define z (* x x))(cond [( z y)(define (u (- y z)))(/ u ( 1 (sqrt u)))][( z y)(define u ( (sqrt (abs x)) y))( u (* u u))]))Advice: Avoid doing the same computation repeatedly! You cando so by computing the intermediary values z x2 andu yp z if z y,u x y if z y.M. MarinALFP
Other useful conditional formswhen, unless, if(when test block)behaves the same as(cond [test block])(unless test block)behaves the same as(cond [test (void)][#t block])RemarkThe branches of the if-form can not be blocks: they must beexpressions:(if test expr1 expr2 )M. MarinALFP
The let form(let ([var1 expr1 ].[varn exprn ])block)is evaluated as follows:1expr1 , . . . , exprn are evaluated to values v1 , . . . , vn .2The definitions var1 v1 , . . . , varn vn are made local toblock.3block is evaluated, and its value is returned as final result.RemarkThis special form is equivalent to((lambda (var1 . . . varn ) body ) expr1 . . . exprn )M. MarinALFP
The let formExamplesM. MarinALFP
The let* form(let* ([var1 expr1 ].[varn exprn ])block)Similar with the let form, but with the following difference:The scope of every local definition[vari expri ]is expri 1 , . . . , exprn , and block.RemarkThis special form is equivalent to(.(lambda (var1 ).(lambda (varn ) body ) exprn ) . expr1 )M. MarinALFP
The let* formExample (let* ([x 1][y ( x 1)])( y x))3; binds x to 1; binds y to the value of ( x 1), which is 2; computes the value of 2 1Note that the following expression can not be evaluated (let ([x 1]; binds x to 1[y ( x 1)]) ;x is undefined here( y x))x: unbound identifier in module in: xM. MarinALFP
The letrec form(letrec ([var1 expr1 ].[varn exprn ])block)Similar with the let* form, but with the following difference:The scope of every local definition(vari expri )is expr1 , . . . , exprn , and block.Thus, var1 , . . . , varn can depend on each other.Example (letrec ([is-even(lambda (n) (if ( n 0) #t (is-odd (- n 1))))][is-odd(lambda (n)(if ( n 0) #f (is-even (- n 1))))])(is-even 5))#fM. MarinALFP
The special forms and and orThey are not functions, they are identifiers of special forms:I (and e1 e2 . en )evaluates e1 , e2 , . . . in this order, until it finds the first eiwhose value is #fIf all ei have non-#f values, return the value of en .Otherwise, return #fI (or e1 e2
Functional programming languages Early history The rst high-level programming language was Fortran (1957). Fortran is an imperative programming language. The second high-level programming language was Lisp (1958). Designed by people interested in AI ("the science and engineering of making intelligent machines");
functional programming style. Adding functional programming facilities to Prolog results in a more powerful language, as they allow higher-order functional expres-sions to be evaluated conveniently within the logic programming environment. And, as will be shown in this thesis, the efficiency of functional programming in logic is
Numeric Functional Programming Functional Data Structures Outline 1 Stuff We Covered Last Time Data Types Multi-precision Verification Array Operations Automatic Differentiation Functional Metaprogramming with Templates 2 Numeric Functional Programming Advanced Functional Programming with Templates Functional Data Structures Sparse Data Structures
The inductive learning and logic programming sides of ILP (cont') Inductive logic programming extends the theory and practice of logic programming by investigating induction rather than deduction as the basic mode of inference - Logic programming theory describes deductive inference from logic formulae provided by the user
BRIEF LADDER LOGIC OVERVIEW Page 2 18.05.2015 1.2 What is Ladder logic? Ladder logic, also known as a Ladder diagram, is a method for programming for Program-mable Logic Controls. Ladder Logic is a standardized type of graphic programming, which is similar to a circuit diagram. Programming with ladder logic is used, in particular, for creat-
Dynamic Logic Dynamic Circuits will be introduced and their performance in terms of power, area, delay, energy and AT2 will be reviewed. We will review the following logic families: Domino logic P-E logic NORA logic 2-phase logic Multiple O/P domino logic Cascode logic
functional and logic programming features are complex in detail so that the concrete design of an integrated functional logic language is a non-trivial task. This is demonstrated by a lot of research work on the semantics, operational principles, and implementation of functional logic languages since more than two decades.
Since logic programming computation is proof search, to study logic pro-gramming means to study proofs. We adopt here the approach by Martin-Lo f [3]. Although he studied logic as a basis for functional programming rather than logic programming, his ideas are more fundamental and there-fore equally applicable in both paradigms. Themost basic .
J. LOGIC PROGRAMMING 1987:4:265-288 265 LOGIC PROGRAMMING WITH EQUATIONS MAARTEN H. VAN EMDEN AND KEITARO YUKAWA* D This paper is a contribution to the amalgamation of logic programming (as embodied in PROLOG) and functional programming (as embodied in
