blob: b5f4189f3d70e83f50a30ca59e891b84578d1182 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
;;; Copyright © 2023 Jakob L. Kreuze <zerodaysfordays@sdf.org>
;;;
;;; This program is free software; you can redistribute it and/or
;;; modify it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 3 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
;;; General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
(define-module (compiler type-inference)
#:use-module ((rnrs base) #:select (assert))
#:use-module (compiler types)
#:use-module (compiler utilities)
#:use-module (ice-9 match)
#:use-module (minikanren mk)
#:use-module (minikanren mkextraforms)
#:use-module (minikanren mkprelude)
#:use-module (srfi srfi-1)
#:use-module (oop goops)
#:export (infer-type
infer-is-a?))
;; Given a pair (x y), assert that y is a valid type for dereferencing.
(define valid-deref
(lambda (x y)
(conde
((== x 'object) (== y 'string))
((== x 'array) (== y 'number))
((== x 'list) (== y 'number)))))
;; `all' but not implemented as a macro.
(define primitive-all
(lambda (xs)
(match xs
(() succeed)
((x) x)
((x xs2 ...)
(conda (x (primitive-all xs2))
(else fail))))))
(define types
'(null bool number string array set object
any))
(define constraints
'(== membero))
(define (normalize form)
"Return FORM with all free variables replaced with a unique `var'"
(map (lambda (x)
(if (and (symbol? x)
(not (memq x types))
(not (memq x constraints)))
(var x)
x))
form))
(define (free-variables form)
"Return all `var' forms in a normalized FORM"
(filter var? form))
(define (mk-variable-for constraints identifier breadcrumb)
"Search CONSTRAINTS for the minikanren variable associated with IDENTIFIER
`breadcrumb' is necessary to uniquely identify `identifier'."
(find (lambda (x)
(eqv? (canonicalize identifier breadcrumb)
(vector-ref x 0)))
(flat-map free-variables constraints)))
(define (evaluate-constraints constraints)
"Make CONSTRAINTS, generated by compiler passes, usable by minikanren"
(map (match-lambda
(('== args ...) (apply == args))
(('membero args ...) (apply membero args)))
constraints))
(define (infer-type identifier breadcrumb scope)
"Return a list of possible types for IDENTIFIER
`breadcrumb' is necessary to uniquely identify `identifier' within `scope'."
(let* ((constraints (collapse-constraints scope))
(constraints (map normalize constraints))
(variables (flat-map free-variables constraints)))
(let* ((x (var 'pairs))
(solutions
(map-inf #f
(lambda (s)
(reify (walk* x s)))
((primitive-all (append ;; (list (== x variables))
`(,(== x (mk-variable-for constraints identifier breadcrumb)))
(evaluate-constraints constraints)))
empty-s))))
(delete-duplicates! solutions))))
(define (infer-is-a? identifier type breadcrumb scope)
"Return whether or not we can infer IDENTIFIER to be a TYPE
`breadcrumb' is necessary to uniquely identify `identifier' within `scope'."
(let ((possible-types (infer-type identifier breadcrumb scope)))
(if (= 1 (length possible-types))
(eqv? type (first possible-types))
#f)))
|
© 2015 - 2026 Jakob L. Kreuze
