程序代写 COMP 481: Functional and Logic Programming

PowerPoint Presentation

2022-09-08

Copyright By PowCoder代写 加微信 powcoder

Introduction

University of the Fraser Valley

COMP 481: Functional and Logic Programming

• course syllabus

• Haskell (functional programming)
• general skills

• creators

• committees

• GHC compiler

• type classes

• Prolog (logic programming)
• knowledge bases

• debugging

• early NLP research

2022-09-08

— Haskell —

general skills

• compiler optimizations

• grammars and parsers

• immutability

• type inference

• lazy evaluation

• academic research

• mathematics

2022-09-08

-Jones (2017) presentation:
• https://www.youtube.com/watch?v=re96UgMk6GQ

• teaching and Microsoft Research at Cambridge

• references: all figures in this presentation

• 1976, Cambridge University has one computer (Pheonix)

• mathematics Cambridge undergraduates

• Simon switched to electrical sciences (engineering)

• both postgrad diploma in computer science

• computer science was just getting established

• between 1 to 4 am: best schedule to get on the one computer!

2022-09-08

context during

Turing Award 1977

Backus earned Turing Award in 1977

• he gave a presentation as part of acceptance

• he proposed two future objectives in computer science

• move away from imperative programming

• design new architectures and continue developing languages
for furthering functional programming

• (new architectures did not turn out to be a good idea)

• these efforts moved research toward writing compilers

2022-09-08

committees

FPCA (1987, Sept) initial meeting of starting Haskell:

• toward teaching, research, and application

• formal syntax and semantics

• freely available

• embodies agreed upon combined contributions
(committee work)

• reduce unnecessary misalignment

• (1990, Apr) Haskell 1.0 Report

user analysis

2022-09-08

GHC compiler

Deep simple principles:

• compiles to an intermediate language

• (Haskell) source language has dozens of
types and 100+ constructors

• (System FC) tiny core language of
3 types and 15 constructors

• purity and laziness

• types and type classes

GHC compiler

Some aspects of its “culture”:

• small user-base for more nimble innovation

• cannot change things as easily when
success drives growth too quickly

• tolerant of GHC bugs

• users react to new features with
excitement for experimentation

• has avoided standardization committees 🤨

2022-09-08

Standardization of a language makes it difficult
to change anything further.

This has led to some very useful concepts…

• laziness makes I/O (a side-effect) impossible

• Philips Wadler explained how monads could
be used for I/O as “actions” in Haskell

• highly influential concept adopted by other languages

2022-09-08

type classes

Another breakthrough:

• (1987–88) type classes proposed by

• implementation for type classes begins with

• allows benefits of similar features as interfaces in OO-programs

• (how would you design code in other languages knowing this?)

Academic research:

• some “relentlessly pursue a slightly unrealistic idea and stick to it”

• this resulted in the benefits Haskell and its developers have provided

Also, implementing a monad type class becomes an extremely
useful programming concept.

2022-09-08

— Prolog —

2022-09-08

knowledge bases

Logical programming:

• use computers to logically prove statements

• code is a set of facts and rules called a knowledge base

• then in an interactive session, write queries

• is the result true or false?

• otherwise, what values make the statement true?

• “execution” tries to search for all such values

• backtracking is both its advantage and disadvantage

SWI-Prolog has a debugger called `trace` to step
through execution.

• difficult to debug otherwise

• Prolog can endlessly apply rules, appearing frozen

• textbook uses older implementation of Prolog
(not SWI-Prolog)

• current maintainer is

• company SWI-Prolog Solutions b.v.

• https://www.swi-prolog.org/blog/solutions.md

• https://swi-prolog.com/

https://www.swi-prolog.org/blog/solutions.md
https://swi-prolog.com/

2022-09-08

NLP research

Invented in Marseille (1972)

• name Prolog suggested by ‘s wife
abbreviates “PROgrammation en LOGique”

Functionality toward proving facts deduced from a set of clauses:

• have programs generating other programs
(queries that are answered true/false by set of clauses and search)

• a variable in a query can be used to “search” for values (unification)

• backtracking chosen to avoid combinatorial explosion in memory use for
searching all branches of possible values for clauses

• this limits programs to finite branching

Up to the programmer to make sure the program terminates!

Thank You!
Questions?

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com